Introduction to Quadratic Residue

定义

令$p$为奇质数。

  • 定义1 对于一个整数$n$,若存在整数$x$,使得$x^2 \equiv n \pmod p$,则称$n$是模$p$的二次剩余,否则称$n$是模$p$的二次非剩余
  • 定义2(勒让德符号) $$\left(\frac{n}{p}\right)=\begin{cases}1, & n是模p的二次剩余 \\ -1, & n是模p的二次非剩余 \\ 0, & p \mid n\end{cases}$$

定理

  • 定理1(欧拉判别准则) $$\left(\frac{n}{p}\right) \equiv n^{\frac{p-1}{2}} \pmod p$$
  • 证明
    若$p \mid n$,则$n \equiv 0 \pmod p$,结论显然成立;
    若$n$是模$p$的二次剩余,则存在$x$满足$x^2 \equiv n \pmod p$,于是$n^{\frac{p-1}{2}} \equiv x^{p-1} \pmod p$,由费马小定理,结论成立;
    若$n$是模$p$的二次非剩余,则不存在$x$满足$x^2 \equiv n \pmod p$。由逆元相关知识,对于任意$1 \le i \le p-1$,存在唯一的$1 \le j \le p-1$,使得$i \neq j$且$ij \equiv n \pmod p$。于是$1$到$p-1$这些数可以两两配对,每一对的乘积都与$n$同余,所以$(p-1)! \equiv n^{\frac{p-1}{2}} \pmod p$,由威尔逊定理,$(p-1)! \equiv -1 \pmod p$,结论成立。

令$1 \le x, y \le p-1$。

  • 定理2 $$x+y \equiv 0 \pmod p \Leftrightarrow x^2 \equiv y^2 \pmod p$$
  • 证明
    $\Rightarrow$:$x+y \equiv 0 \pmod p \Rightarrow x \equiv -y \pmod p$,两边平方即得。
    $\Leftarrow$: $x^2 \equiv y^2 \pmod p \Rightarrow x^2-y^2 \equiv (x-y)(x+y) \equiv 0 \pmod p$,显然$x-y \nmid p$,于是有$x+y \mid p \Rightarrow x+y \equiv 0 \pmod p$。
  • 定理3 在$1$到$p-1$中,模$p$的二次剩余和二次非剩余的个数均为$\frac{p-1}{2}$。
  • 证明
    定理2,$1$到$p-1$中有且仅有$\frac{p-1}{2}$个不同的二次剩余,其余$\frac{p-1}{2}$个即为二次非剩余。并且对于每一个二次剩余$n$,都存在两个不同的$x$满足$x^2 \equiv n \pmod p$。

算法

给定整数$n$和奇质数$p$,求满足$x^2 \equiv n \pmod p$的$x$。

  1. 欧拉判别准则判断$n$是否为模$p$的二次剩余,如果不是则返回$-1$表示无解,如果是$0$则返回$0$;
  2. 从$1$到$p-1$中随机选一个整数$a$,使得$a^2-n$为模$p$的二次非剩余(根据定理3,随机的次数不会太多);
  3. 令$\omega \equiv a^2-n \pmod p$,取$x \equiv (a+\sqrt{\omega})^{\frac{p-1}{2}} \pmod p$,返回$x$(这里$\sqrt{\omega}$可以理解成虚数)。
  • 引理1 $$\omega^{\frac{p}{2}} \equiv -\omega^{\frac{1}{2}} \pmod p$$
  • 证明
    欧拉判别准则,显然成立。
  • 引理2 $$(a+b)^p \equiv a^p+b^p \pmod p$$
  • 证明
    $(a+b)^p \equiv \sum_{i=0}^p {p \choose i}a^ib^{p-i}$,由于$p$是奇质数,所以当且仅当$i=0$或$i=p$时${p \choose i}$没有因子$p$,于是成立。
  • 算法证明
    $$\begin{align} x^2 & \equiv (a+\sqrt{\omega})^{p-1} \\ & \equiv (a+\sqrt{\omega})^p(a+\sqrt{\omega}) \\ & \equiv (a^p+\omega^{\frac{p}{2}})(a+\sqrt{\omega}) \\ & \equiv (a-\sqrt{\omega})(a+\sqrt{\omega}) \\ & \equiv a^2-\omega \equiv n \pmod p \end{align}$$
    由于$x^2 \equiv n \pmod p$有且仅有两根,且都不含$\sqrt{\omega}$项,而由算法给出的$x$是方程的一个根,所以它不含$\sqrt{\omega}$项。

代码

const int MOD = 998244353;
 
#define rnd (1ll * rand() * rand() % MOD)

struct Field {
    int a, b, w;
    Field(int _a = 0, int _b = 0, int _w = 0) : a(_a), b(_b), w(_w) {}
    friend Field operator*(const Field &x, const Field &y) {
        return Field((1ll * x.a * y.a + 1ll * x.b * y.b % MOD * x.w) % MOD, (1ll * x.a * y.b + 1ll * x.b * y.a) % MOD, x.w);
    }
} a[N];

int power(int a, int b) {
    int ret = 1;
    for (; b; b >>= 1) {
        if (b & 1) {
            ret = 1ll * ret * a % MOD;
        }
        a = 1ll * a * a % MOD;
    }
    return ret;
}
 
Field power(Field a, int b) {
    Field ret = Field(1, 0, a.w);
    for (; b; b >>= 1) {
        if (b & 1) {
            ret = ret * a;
        }
        a = a * a;
    }
    return ret;
}
 
int quadratic(int t) {
    int l = power(t, MOD >> 1);
    return l > 1 ? l - MOD : l;
}
 
int solve(int t) {
    int l = quadratic(t);
    if (l < 1) {
        return l;
    }
    int a = rnd, w = (MOD + 1ll * a * a - t) % MOD;
    for (; ~quadratic(w); a = rnd, w = (MOD + 1ll * a * a - t) % MOD) ;
    return power(Field(a, 1, w), MOD + 1 >> 1).a;
}

Four Loop

题目描述

Given two sequences $a$ and $b$ of equal length $n$, find the

$$\sum_{x=1}^n \sum_{y=1}^n \sum_{z=1}^n \sum_{w=1}^n (a_x+a_y+a_z+a_w)^{(b_x \oplus b_y \oplus b_z \oplus b_w)}$$

题意概述

给定两个长度为$n$的序列$a$和$b$,求$\sum_{x=1}^n \sum_{y=1}^n \sum_{z=1}^n \sum_{w=1}^n (a_x+a_y+a_z+a_w)^{(b_x \oplus b_y \oplus b_z \oplus b_w)}$。

数据范围:$1 \le n \le 10^5, \; 1 \le a_i \le 500, \; 1 \le b_i \le 500$。

算法分析

$a_x+a_y+a_z+a_w$的取值范围为$[4,2000]$,$b_x \oplus b_y \oplus b_z \oplus b_w$的取值范围为$[0,511]$,可以分别计算每种情况出现的次数再求和。

令$f_{1,i,j}$表示有多少个$x$满足$a_x=i \land b_x=j$。对于$k \ge 2$,令

$$f_{k,i,j}=\sum_{i_1+i_2=i} \sum_{j_1 \oplus j_2=j} f_{k-1,i_1,j_1}f_{1,i_2,j_2}$$

$f_{4,i,j}$即要求的每种情况出现的次数。转移方程在一维上是乘法卷积,另一维上是异或卷积,可以分别用FFT和FWT进行处理。总时间复杂度为$O(a_{\max}b_{\max}\log(a_{\max}b_{\max}))$。

代码

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
 
int const N = 100005, M = 512, MOD = 998244353, G = 3, INV2 = 499122177;
 
int a[N], b[N], rev[M << 2];
 
int power(int a, int b) {
    int ret = 1;
    for (; b; b >>= 1) {
        if (b & 1) {
            ret = 1ll * ret * a % MOD;
        }
        a = 1ll * a * a % MOD;
    }
    return ret;
}
 
int wn[M << 2], A[M << 2], f[M << 2][M];
 
void init(int n) {
    int len = 1, p = 0;
    for (; len < n; len <<= 1, ++p) ;
    for (int i = 1; i < len; ++i) {
        rev[i] = rev[i >> 1] >> 1 | (i & 1) << p - 1;
    }
    wn[0] = 1, wn[1] = power(G, (MOD - 1) / len);
    for (int i = 2; i < len >> 1; ++i) {
        wn[i] = 1ll * wn[i - 1] * wn[1] % MOD;
    }
}
 
void fft(int *a, int len, bool inv = 0) {
    for (int i = 0; i < len; ++i) {
        if (i < rev[i]) {
            std::swap(a[i], a[rev[i]]);
        }
    }
    for (int i = 1; i < len; i <<= 1) {
        for (int j = 0; j < len; j += i << 1) {
            for (int k = 0; k < i; ++k) {
                int x = a[j + k], y = 1ll * wn[len / (i << 1) * k] * a[j + i + k] % MOD;
                a[j + k] = (x + y) % MOD;
                a[j + i + k] = (MOD + x - y) % MOD;
            }
        }
    }
    if (inv) {
        std::reverse(a + 1, a + len);
        int inv = power(len, MOD - 2);
        for (int i = 0; i < len; ++i) {
            a[i] = 1ll * a[i] * inv % MOD;
        }
    }
}
 
void fwt(int *a, int len, bool inv = 0) {
    for (int i = 1; i < len; i <<= 1) {
        for (int j = 0; j < len; j += i << 1) {
            for (int k = 0; k < i; ++k) {
                int x = a[j + k], y = a[j + i + k];
                a[j + k] = (x + y) % MOD;
                a[j + i + k] = (MOD + x - y) % MOD;
                if (inv) {
                    a[j + k] = 1ll * a[j + k] * INV2 % MOD;
                    a[j + i + k] = 1ll * a[j + i + k] * INV2 % MOD;
                }
            }
        }
    }
}
 
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
    }
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &b[i]);
        f[a[i]][b[i]] = f[a[i]][b[i]] + 1;
    }
    init(M << 2);
    for (int i = 0; i < M << 2; ++i) {
        for (int j = 0; j < M; ++j) {
            A[j] = f[i][j];
        }
        fwt(A, M);
        for (int j = 0; j < M; ++j) {
            f[i][j] = A[j];
        }
    }
    for (int i = 0; i < M; ++i) {
        for (int j = 0; j < M << 2; ++j) {
            A[j] = f[j][i];
        }
        fft(A, M << 2);
        for (int j = 0; j < M << 2; ++j) {
            f[j][i] = A[j];
        }
    }
    for (int i = 0; i < M << 2; ++i) {
        for (int j = 0; j < M; ++j) {
            f[i][j] = power(f[i][j], 4);
        }
    }
    for (int i = 0; i < M << 2; ++i) {
        for (int j = 0; j < M; ++j) {
            A[j] = f[i][j];
        }
        fwt(A, M, 1);
        for (int j = 0; j < M; ++j) {
            f[i][j] = A[j];
        }
    }
    for (int i = 0; i < M; ++i) {
        for (int j = 0; j < M << 2; ++j) {
            A[j] = f[j][i];
        }
        fft(A, M << 2, 1);
        for (int j = 0; j < M << 2; ++j) {
            f[j][i] = A[j];
        }
    }
    int ans = 0;
    for (int i = 0; i < M << 2; ++i) {
        for (int j = 0; j < M; ++j) {
            if (f[i][j]) {
                ans = (ans + 1ll * f[i][j] * power(i, j)) % MOD;
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}

Bitwise XOR

题目描述

Given a sequence $a$ and an empty sequence $b$, each element in $a$ is added to $b$ with probability $P$ (independently to the other elements). Denote $s=\bigoplus_{i=1}^{|b|} b_i$, where $\oplus$ denotes bitwise xor and $s=0$ if $b$ is empty. Find the expected value of $s^2$.

题意概述

给定一个长度为$n$的序列$a$,其中每个数都有$P$的概率被选中。令被选中的数的异或和为$s$。求$s^2$的期望。

数据范围:$1 \le n \le 10^5, \; 0 \le a_i \lt 10^9+7$。

算法分析

令$P(s)$表示异或和为$s$的概率。把$s$用二进制表示,最低位为第$0$位。

$$\begin{align} \sum_s s^2P(s) &= \sum_s (\sum_{i=0}^{29} [s二进制第i位为1] 2^i)^2P(s) \\ &= \sum_s P(s) \sum_{i=0}^{29} [s二进制第i位为1] 2^i \sum_{j=0}^{29} [s二进制第j位为1] 2^j \\ &= \sum_s P(s) \sum_{i=0}^{29} \sum_{j=0}^{29} [s二进制第i位和第j位都为1] 2^{i+j} \\ &= \sum_{i=0}^{29} \sum_{j=0}^{29} P(s二进制第i位和第j位都为1) 2^{i+j} \end{align}$$

先枚举$i$和$j$,令$f_{k,0/1,0/1}$表示从前$k$个数中选,异或和第$i$位、第$j$为分别为$0/1$、$0/1$的概率,对$f_{n,1,1}2^{i+j}$求和即为答案。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
 
int const N = 100005, MOD = 1000000007;
 
int a[N], f[N][2][2];
 
int power(int a, int b) {
    int ret = 1;
    for (; b; b >>= 1) {
        if (b & 1) {
            ret = 1ll * ret * a % MOD;
        }
        a = 1ll * a * a % MOD;
    }
    return ret;
}
 
int main() {
    int n, x, y;
    scanf("%d%d%d", &n, &x, &y);
    int p = 1ll * x * power(y, MOD - 2) % MOD, q = (MOD + 1 - p) % MOD;
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
    }
    int ans = 0, ans2 = 0;
    f[0][0][0] = 1;
    for (int i = 0; i < 30; ++i) {
        for (int j = i; j < 30; ++j) {
            for (int k = 1; k <= n; ++k) {
                for (int _i = 0; _i < 2; ++_i) {
                    for (int _j = 0; _j < 2; ++_j) {
                        int __i = _i ^ (a[k] >> i & 1);
                        int __j = _j ^ (a[k] >> j & 1);
                        f[k][_i][_j] = (1ll * f[k - 1][_i][_j] * q + 1ll * f[k - 1][__i][__j] * p) % MOD;
                    }
                }
            }
            ans = (ans + (1ll << i + j + (i != j)) % MOD * f[n][1][1]) % MOD;
        }
    }
    printf("%d\n", ans);
    return 0;
}

Unbalanced Coin

题目描述

You have an unbalanced coin, the state of which (head or tail) after tossing depends on the previous state. If the head side is up now, the probability that the coin is still head up after tossing is $p$, and the probability that the tail side comes up is $1-p$. Similarly, if the tail side is up now, the probability that the coin is still tail up after tossing is $p$, and the probability that the head side comes up is $1-p$.

Assume the coin is head up initially. You will then toss it for $n$ times, during these $n$ times, every time the head side is up, you will get one score. What is the probability that you will get exactly $k$ score for $k=0,1,2,\cdots,n$?

题意概述

有一枚初始正面朝上的硬币。每次投掷时,硬币有$p$的概率保持不变,$1-p$的概率翻面。求$n$次投掷后,正面朝上的总次数分别为$0,1,2,\cdots,n$的概率。

数据范围:$1 \le n \le 10^5$。

算法分析

令$f_{i,0/1,j}$表示$i$次投掷后,硬币正面/反面朝上,且正面朝上的总次数为$j$概率。容易想到转移方程:

$$\begin{align} f_{i,0,j} &= f_{i-1,0,j-1} \times p+f_{i-1,1,j-1} \times (1-p) \\ f_{i,1,j} &= f_{i-1,0,j} \times (1-p)+f_{i-1,1,j} \times p \end{align}$$

这样直接转移的复杂度是$O(n^2)$,考虑如何优化。

令$f_{i,0/1}$的普通型生成函数为$F_{i,0/1}$,即$F_{i,0/1}=\sum_{j=0}^i f_{i,0/1,j}x^j$。则上述转移方程可表示为:

$$\begin{align} F_{i,0} &= F_{i-1,0} \times px+F_{i-1,1} \times (1-p)x \\ F_{i,1} &= F_{i-1,0} \times (1-p)+F_{i-1,1} \times p \end{align}$$

容易想到其矩阵形式:

$$\begin{equation} \left[\begin{matrix} px & (1-p)x \\ 1-p & p\end{matrix}\right] \left[\begin{matrix} F_{i-1,0} \\ F_{i-1,1} \end{matrix}\right]= \left[\begin{matrix} F_{i,0} \\ F_{i,1} \end{matrix}\right]\end{equation}$$

如此便可以用矩阵快速幂来优化了。其中多项式乘法需要用FFT计算。

代码

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
 
int const N = 200005;
double const PI = acos(-1);
 
int rev[N];
 
struct Complex {
    double a, b;
    Complex(double _a = 0, double _b = 0) : a(_a), b(_b) {}
    friend Complex operator+(Complex const &x, Complex const &y) {
        return Complex(x.a + y.a, x.b + y.b);
    }
    friend Complex operator-(Complex const &x, Complex const &y) {
        return Complex(x.a - y.a, x.b - y.b);
    }
    friend Complex operator*(Complex const &x, Complex const &y) {
        return Complex(x.a * y.a - x.b * y.b, x.a * y.b + x.b * y.a);
    }
    friend Complex operator/(Complex const &x, double const &y) {
        return Complex(x.a / y, x.b / y);
    }
} wn[N], A[2][2][N], B[2][2][N], C[2][2][N];
 
int init(int n) {
    int len = 1, p = 0;
    for (; len < n; len <<= 1, ++p) ;
    for (int i = 1; i < len; ++i) {
        rev[i] = rev[i >> 1] >> 1 | (i & 1) << p - 1;
    }
    for (int i = 0; i < len >> 1; ++i) {
        wn[i] = Complex(cos(2 * PI / len * i), sin(2 * PI / len * i));
    }
    return len;
}
 
void fft(Complex *a, int len, bool inv = 0) {
    for (int i = 0; i < len; ++i) {
        if (i < rev[i]) {
            std::swap(a[i], a[rev[i]]);
        }
    }
    for (int i = 1; i < len; i <<= 1) {
        for (int j = 0; j < len; j += i << 1) {
            for (int k = 0; k < i; ++k) {
                Complex x = a[j + k], y = wn[len / (i << 1) * k] * a[j + i + k];
                a[j + k] = x + y;
                a[j + i + k] = x - y;
            }
        }
    }
    if (inv) {
        std::reverse(a + 1, a + len);
        for (int i = 0; i < len; ++i) {
            a[i] = a[i] / len;
        }
    }
}
 
struct Matrix {
    int n[2][2];
    double *a[2][2];
 
    friend Matrix operator*(Matrix const &x, Matrix const &y) {
        int len = init(x.n[0][0] + y.n[0][0] - 1);
        for (int i = 0; i < 2; ++i) {
            for (int j = 0; j < 2; ++j) {
                for (int k = 0; k < len; ++k) {
                    A[i][j][k] = k < x.n[i][j] ? x.a[i][j][k] : 0;
                    B[i][j][k] = k < y.n[i][j] ? y.a[i][j][k] : 0;
                    C[i][j][k] = 0;
                }
                fft(A[i][j], len);
                fft(B[i][j], len);
            }
        }
        for (int i = 0; i < 2; ++i) {
            for (int j = 0; j < 2; ++j) {
                for (int k = 0; k < 2; ++k) {
                    for (int l = 0; l < len; ++l) {
                        C[i][j][l] = C[i][j][l] + A[i][k][l] * B[k][j][l];
                    }
                }
                fft(C[i][j], len, 1);
            }
        }
        Matrix ret;
        for (int i = 0; i < 2; ++i) {
            for (int j = 0; j < 2; ++j) {
                ret.n[i][j] = 0;
                for (int k = 0; k < 2; ++k) {
                    ret.n[i][j] = std::max(ret.n[i][j], x.n[i][k] + y.n[k][j] - 1);
                }
                ret.a[i][j] = new double[ret.n[i][j]];
                for (int k = 0; k < ret.n[i][j]; ++k) {
                    ret.a[i][j][k] = C[i][j][k].a;
                }
            }
        }
        return ret;
    }
} base, ans;
 
int main() {
    int n;
    double p;
    scanf("%d%lf", &n, &p);
    base.n[0][0] = base.n[0][1] = 2;
    base.n[1][0] = base.n[1][1] = 1;
    base.a[0][0] = new double[2];
    base.a[0][0][0] = 0;
    base.a[0][0][1] = p;
    base.a[0][1] = new double[2];
    base.a[0][1][0] = 0;
    base.a[0][1][1] = 1 - p;
    base.a[1][0] = new double;
    base.a[1][0][0] = 1 - p;
    base.a[1][1] = new double;
    base.a[1][1][0] = p;
    ans.n[0][0] = ans.n[1][1] = 1;
    ans.a[0][0] = new double;
    ans.a[0][0][0] = 1;
    ans.a[1][1] = new double;
    ans.a[1][1][0] = 1;
    int b = n;
    for (; b;) {
        if (b & 1) {
            ans = ans * base;
        }
        if (b >>= 1) {
            base = base * base;
        }
    }
    for (int i = 0; i <= n; ++i) {
        printf("%.10f\n", ans.a[0][0][i] + ans.a[1][0][i]);
    }
    return 0;
}

Conquer the Polygon

题目描述

You have a convex polygon. The vertices of the polygon are successively numbered from $1$ to $n$. You also have a triangulation of this polygon, given as a list of $n-3$ diagonals.

There will be $2n-3$ undirected edges in the graph: $n-3$ edges in the triangulation and $n$ edges on the side of the polygon.

You can choose to conquer some vertices, and if you choose to conquer a vertex, you will conquer all the edges linked to this vertex.

Write a program to determine the minimum number of vertices you need to choose such that you can conquer all the edges. Note that you are not required to conquer all the vertices.

题意概述

给定一个$n$边形的三角剖分,求它的最小点覆盖。

数据范围:$4 \le n \le 10^5$。

算法分析

考虑一个度数为$2$的点:

  • 如果这个点已被选择,那么与它相邻的两条边都已被覆盖;
  • 否则,为了覆盖与它相邻的边,最优方案是选择与它相邻的两个点。

于是可以将这个点和与它相邻的边删去,又会得到新的度数为$2$的点。可以用类似拓扑排序的方法来维护。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
 
int const N = 100005;
int nume, h[N], in[N], used[N], que[N];
struct Edge {
    int v, nxt;
} e[N << 2];
 
void add_edge(int u, int v) {
    e[++nume] = (Edge) {v, h[u]};
    h[u] = nume;
}
 
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= 2 * n - 3; ++i) {
        int u, v;
        scanf("%d%d", &u, &v);
        add_edge(u, v);
        add_edge(v, u);
        ++in[u];
        ++in[v];
    }
    int qb = 0, qe = 0;
    for (int i = 1; i <= n; ++i) {
        if (in[i] == 2) {
            que[qe++] = i;
        }
    }
    for (; qb < qe;) {
        int cur = que[qb++];
        if (!used[cur]) {
            for (int i = h[cur]; i; i = e[i].nxt) {
                if (in[e[i].v] > 2) {
                    used[e[i].v] = 1;
                }
            }
        }
        for (int i = h[cur]; i; i = e[i].nxt) {
            --in[cur];
            --in[e[i].v];
            if (in[e[i].v] == 2) {
                que[qe++] = e[i].v;
            }
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        ans += used[i];
    }
    printf("%d\n", ans);
    return 0;
}

BBQ

题目描述

You are a master of barbeque, and now you are trying to string dumplings with a bamboo stick.

The dumplings are placed in a $n \times m$ grid. Each grid contains exactly one dumpling. The color of each dumpling is red ("R"), green ("G") or white ("W").

You can choose three consecutive grids from left to right, or from top to bottom, and string the corresponding dumplings into a string from left to right or from top to bottom. So there will be exactly three dumplings on a string, let’s denote a string of dumpling by their colors in order.

Now, you want to make strings "RGW" as many as possible. Note that the dumplings can not be reused in multiple strings. So how many strings "RGW" can you make?

题意概述

给定一个$n \times m$的字符矩阵。每次可以从上到下或从左到右取连续三个字符构成一个字符串,每个字符只能取一次。求最多能取几个RGW

数据范围:$1 \le n, m \le 3000$。

算法分析

只需考虑最多能取几个G。可以发现,只有在同一条与副对角线平行的直线上的G会相互影响。分别计算每一条直线,令$f_{i, 0/1/2}$表示第$i$个位置不取/从左到右取/从上到下取的情况下,前$i$个位置最多能取几个G。最后把所有直线的结果加起来得到答案。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
 
int const N = 3005;
char mp[N][N];
int f[N][N][3];
 
int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) {
        scanf("%s", mp[i] + 1);
    }
    for (int k = 2; k <= n + m; ++k) {
        for (int i = 1; i < k; ++i) {
            int j = k - i;
            if (i <= n && j <= m) {
                f[i][j][0] = std::max(f[i - 1][j + 1][0], std::max(f[i - 1][j + 1][1], f[i - 1][j + 1][2]));
                if (mp[i][j - 1] == 'R' && mp[i][j] == 'G' && mp[i][j + 1] == 'W') {
                    f[i][j][1] = std::max(f[i - 1][j + 1][0], f[i - 1][j + 1][1]) + 1;
                }
                if (mp[i - 1][j] == 'R' && mp[i][j] == 'G' && mp[i + 1][j] == 'W') {
                    f[i][j][2] = std::max(f[i - 1][j + 1][0], f[i - 1][j + 1][2]) + 1;
                }
            }
        }
    }
    int ans = 0;
    for (int i = 1; i < n; ++i) {
        ans += std::max(f[i][1][0], std::max(f[i][1][1], f[i][1][2]));
    }
    for (int i = 1; i <= m; ++i) {
        ans += std::max(f[n][i][0], std::max(f[n][i][1], f[n][i][2]));
    }
    printf("%d\n", ans);
    return 0;
}