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;
}

Tsr and Variance

题目描述

Tsr is a cute boy with handsome moustache.

You are given a sequence with length $n$. Tsr wants you to calculate the sum of variance of each successive subsequence. Note: The variance in this problem should’t be divided by length.

Recall $\overline{a}_{l, r}=\frac{1}{r-l+1} \sum_{i=l}^r a_i$. Then you are supposed to calculate $\sum_{i=1}^n \sum_{j=i}^n \sum_{k=i}^j (a_k-\overline{a}_{i, j})^2$.

题意概述

给定一个长度为$n$的序列,求$\sum_{i=1}^n \sum_{j=i}^n \sum_{k=i}^j (a_k-\overline{a}_{i, j})^2$。有$T$组数据。

数据范围:$1 \le T \le 20, \; 1 \le n \le 10000, \; 1 \le a_i \le 10$。

算法分析

$$\begin{align} \sum_{i=1}^n \sum_{j=i}^n \sum_{k=i}^j (a_k-\overline{a}_{i, j})^2 &= \sum_{i=1}^n \sum_{j=i}^n \sum_{k=i}^j (a_k^2-2a_k \overline{a}_{i, j}+\overline{a}_{i, j}^2) \\ &= \sum_{k=1}^n \sum_{i=1}^k \sum_{j=k}^n a_k^2-2\sum_{i=1}^n \sum_{j=i}^n \overline{a}_{i, j} \sum_{k=i}^j a_k+ \sum_{i=1}^n \sum_{j=i}^n (j-i+1) \overline{a}_{i, j}^2 \\ &= \sum_{k=1}^n k(n-k+1)a_k^2-\sum_{i=1}^n \sum_{j=i}^n (j-i+1) \overline{a}_{i, j}^2 \end{align}$$

前一项可以在$O(n)$时间内求出,只需考虑如何求后一项。令$s_i=\sum_{j=1}^i a_j$。

$$\begin{align} \sum_{i=1}^n \sum_{j=i}^n (j-i+1) \overline{a}_{i, j}^2 &= \sum_{j=1}^n \sum_{i=1}^j \frac{(s_j-s_{i-1})^2}{j-i+1} \\ &= \sum_{j=1}^n \sum_{i=1}^j \frac{s_j^2-2s_js_{i-1}+s_{i-1}^2}{j-i+1} \\ &= \sum_{j=1}^n s_j^2 \sum_{i=1}^j \frac{1}{i}-2\sum_{j=1}^n s_j \sum_{i=1}^j \frac{s_{i-1}}{j-(i-1)}+\sum_{j=1}^n \sum_{i=1}^j \frac{s_{i-1}^2}{j-(i-1)} \end{align}$$

第一项也可以在$O(n)$时间内求出,而后面两项都是卷积的形式,可以用FFT在$O(n\log n)$时间内求出。

代码

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>

int const N = 10005, T = 400005;
double const PI = acos(-1);

int a[N], rev[T];

struct Point {
    double x, y;
    Point(double _x = 0, double _y = 0) : x(_x), y(_y) {}
    friend Point const operator + (Point const &a, Point const &b) {
        return Point(a.x + b.x, a.y + b.y);
    }
    friend Point const operator - (Point const &a, Point const &b) {
        return Point(a.x - b.x, a.y - b.y);
    }
    friend Point const operator * (Point const &a, Point const &b) {
        return Point(a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x);
    }
    friend Point const operator / (Point const &a, double const &n) {
        return Point(a.x / n, a.y / n);
    }
} wn[T], A[T], B[T], C[T];

int init(int n) {
    int m = n, l = 0;
    for (n = 1; n <= m; n <<= 1, ++l) ;
    for (int i = 1; i < n; ++i) {
        rev[i] = rev[i >> 1] >> 1 | (i & 1) << l - 1;
    }
    for (int i = 0; i < n >> 1; ++i) {
        wn[i] = Point(cos(2 * PI / n * i), sin(2 * PI / n * i));
    }
    return n;
}

void fft(Point *a, int n, int inv = 0) {
    for (int i = 0; i < n; ++i) {
        if (i < rev[i]) {
            std::swap(a[i], a[rev[i]]);
        }
    }
    for (int i = 1; i < n; i <<= 1) {
        for (int j = 0; j < n; j += i << 1) {
            for (int k = 0; k < i; ++k) {
                Point x = a[j + k], y = wn[n / (i << 1) * k] * a[j + k + i];
                a[j + k] = x + y;
                a[j + k + i] = x - y;
            }
        }
    }
    if (inv) {
        std::reverse(a + 1, a + n);
        for (int i = 0; i < n; ++i) {
            a[i] = a[i] / n;
        }
    }
}

int main() {
    int T;
    scanf("%d", &T);
    for (; T--;) {
        int n;
        scanf("%d", &n);
        double ans = 0;
        for (int i = 1; i <= n; ++i) {
            scanf("%d", &a[i]);
            ans += 1. * a[i] * a[i] * i * (n - i + 1);
            a[i] += a[i - 1];
        }
        double sum = 0;
        for (int i = 1; i <= n; ++i) {
            sum += 1. / i;
            ans -= sum * a[i] * a[i];
        }
        int len = init(n << 1);
        for (int i = 0; i < n; ++i) {
            A[i] = Point(a[i]);
            B[i] = Point(1. * a[i] * a[i]);
            C[i] = Point(1. / (i + 1));
        }
        for (int i = n; i < len; ++i) {
            A[i] = B[i] = C[i] = Point(0);
        }
        fft(A, len);
        fft(B, len);
        fft(C, len);
        for (int i = 0; i < len; ++i) {
            A[i] = A[i] * C[i];
            B[i] = B[i] * C[i];
        }
        fft(A, len, 1);
        fft(B, len, 1);
        for (int i = 0; i < n; ++i) {
            ans += 2 * a[i + 1] * A[i].x - B[i].x;
        }
        printf("%.10f\n", ans);
    }
    return 0;
}

Fence

题目描述

A team of $K$ workers should paint a fence which contains $N$ planks numbered from $1$ to $N$ from left to right. Each worker $i$ should sit in front of the plank $S_i$ and he may paint only a compact interval (this means that the planks from the interval should be consecutive). This interval should contain the $S_i$ plank. Also a worker should not paint more than $L_i$ planks and for each painted plank he should receive $P_i$\$. A plank should be painted by no more than one worker. All the numbers $S_i$ should be distinct.

Being the team’s leader you want to determine for each worker the interval that he should paint, knowing that the total income should be maximal. The total income represents the sum of the workers personal income.

Write a program that determines the total maximal income obtained by the $K$ workers.

题意概述

$K$个工人要粉刷一面长度为$N$的篱笆,第$i$个工人要么不粉刷,要么粉刷一段连续且长度不超过$L_i$的包含第$S_i$块木板的篱笆,他每粉刷一块木板可以获得$P_i$的报酬。每一块木板要么不被粉刷,要么仅被一个工人粉刷。求所有工人获得的总报酬的最大值。

数据范围:$1 \le K \le 100, \; 1 \le N \le 16000$。

算法分析

令$f_{i, j}$表示前$i$个工人粉刷前$j$块木板(不一定全刷)的最大报酬,则可分三种情况讨论:

  • 第$i$个工人不粉刷,$f_{i, j}=f_{i-1, j}$;
  • 第$j$块木板不被粉刷,$f_{i, j}=f_{i, j-1}$;
  • 第$i$个工人粉刷第$(k+1)$到第$j$块木板,$f_{i, j}=f_{i-1, k}+(j-k) \times P_i$。

在第三种情况中,转移方程变形后得$f_{i, j}=(f_{i-1, k}-k \times P_i)+j \times P_i$,$f_{i-1, k}-k \times P_i$与$j$无关,$j \times P_i$与$k$无关,因此对于确定的$i$和$j$,方程后半部分为常数,只要求前半部分的最大值。因为前半部分只与$k$有关,所以可以用单调队列维护其最大值。注意$k$要满足的条件是$k+1 \le S_i \le j$与$j-(k+1)+1 \le L_i$,即$j-L_i \le k \lt S_i$。算法的时间复杂度为$O(KN)$。

代码

#include <cstdio>
#include <algorithm>

int const K = 105, N = 16005;
int f[K][N];
struct Carpenter {
    int l, p, s;
    bool operator < (Carpenter const &t) const {
        return s < t.s;
    }
} c[K];
std::pair<int, int> que[N];

int main() {
    int n, k;
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= k; ++i) {
        scanf("%d%d%d", &c[i].l, &c[i].p, &c[i].s);
    }
    std::sort(c + 1, c + k + 1);
    for (int i = 1; i <= k; ++i) {
        int qb = 0, qe = 0;
        for (int j = 0; j < c[i].s; ++j) {
            for (; qb < qe && que[qe - 1].first <= f[i - 1][j] - c[i].p * j; --qe) ;
            que[qe++] = std::make_pair(f[i - 1][j] - c[i].p * j, j);
        }
        for (int j = 1; j <= n; ++j) {
            f[i][j] = std::max(f[i - 1][j], f[i][j - 1]);
            if (c[i].s <= j && j < c[i].s + c[i].l) {
                for (; qb < qe && que[qb].second < j - c[i].l; ++qb) ;
                f[i][j] = std::max(f[i][j], que[qb].first + c[i].p * j);
            }
        }
    }
    printf("%d\n", f[k][n]);
    return 0;
}

Primes

题目描述

This is an interactive problem.
For two positive integers $x, y$, we define $\pi(x, y)$ to be the number of distinct primes that divide both $x$ and $y$. For example $\pi(2, 3) = 0, \; \pi(8, 16) = 1$ and $\pi(30, 105) = 2$.
For two positive integers $a, b$, where $a \le b$, we define $S(a, b)$ to be the sum of values $\pi(x, y)$ over all pairs of integers $(x, y)$ satisfying $a \le x \lt y \le b$.
Your task is to compute the values $S(a, b)$ for many query pairs $(a, b)$. To make your task more challenging, all the queries have to be answered online.

题意概述

给定两个整数$a, b$,定义$\pi(x, y)$为所有整除$x$和$y$的质数的个数,$S(a, b)$为所有满足$a \le x \lt y \le b$的$\pi(x, y)$的和,求$S(a, b)$。有$q$组询问,强制在线。

数据范围:$1 \le q \le 50000, \; 1 \le a \le b \le 10^6$。

算法分析

分别考虑每个质数对答案的贡献。若在区间$[a, b]$中有$k$个数能被质数$p$整除,则$p$对答案的贡献为${k \choose 2}$。

首先筛出所有质数。但是每次询问直接枚举质数会超时。考虑对于一个整数$n$,$\lfloor {n \over i} \rfloor$只有$O(\sqrt{n})$种不同的取值。因此可以对$\lfloor {a \over i} \rfloor$和$\lfloor {b \over i} \rfloor$进行分段枚举。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>

int const N = 1000005;

int tp, prime[N], rec[N], vis[N], sum[N];

void init() {
    for (int i = 2; i < N; ++i) {
        if (!vis[i]) {
            prime[tp++] = i;
        }
        for (int j = 0; j < tp && i * prime[j] < N; ++j) {
            vis[i * prime[j]] = 1;
            if (i % prime[j] == 0) {
                break;
            }
        }
    }
    for (int i = 2; i < N; ++i) {
        sum[i] = sum[i - 1] + !vis[i];
    }
}

int main() {
    init();
    int q;
    scanf("%d", &q);
    for (; q--;) {
        int a, b;
        scanf("%d%d", &a, &b);
        long long ans = 0;
        for (int i = 0; i < tp && prime[i] < b;) {
            int cnt = b / prime[i] - (a - 1) / prime[i];
            int nxt = 1e9;
            if (b / prime[i]) {
                nxt = std::min(nxt, b / (b / prime[i]));
            }
            if ((a - 1) / prime[i]) {
                nxt = std::min(nxt, (a - 1) / ((a - 1) / prime[i]));
            }
            ans += 1ll * cnt * (cnt - 1) / 2 * (sum[nxt] - i);
            i = sum[nxt];
        }
        printf("%lld\n", ans);
        fflush(stdout);
    }
    return 0;
}

Black-White Balls

题目描述

$n$ black and white balls were put into a bag. Petya doesn’t know exactly how many black balls are there among them. He knows, however, that there are $0, 1, \ldots, n$ black balls among all balls in the bag with equal probability.
Petya took $l$ balls from the bag at random, and $l_1$ of them turned out black, while $l_2$ other turned out white ($l_1+l_2=l$). Now he wants to predict how many black balls were there initially in the bag. Of course, if $l \lt n$, he can’t be sure in his prediction, but he wants to predict a segment $[a, b]$, such that the amount $k$ of black balls belongs to it with probability at least $p$.
You are given $n, l_1, l_2$ and $p$, and you must find such $a$ and $b$ that $b-a$ is minimal possible. If there are several such pairs $(a, b)$, choose the one with the smallest $a$.

题意概述

袋子里有$n$个球,每个球可能是黑色或白色。已知黑球个数在$0, 1, \ldots, n$之间等概率分布。现在从中取出$l$个球,其中有$l_1$个黑球和$l_2$个白球($l_1+l_2=l$)。要求找到一个最短的区间$[a, b]$,使得黑球个数在$[a, b]$中的概率至少为${p \over 100}$。若有多个这样的区间,输出$a$最小的。
数据范围:$1 \le n \le 50, \; 0 \le l_1 \le n, \; 0 \le l_2 \le n-l_1, \; 0 \le p \le 100$。

算法分析

令事件$A$为取出的$l$个球中有$l_1$个黑球,事件$B_i$为袋子里有$i$个黑球。根据贝叶斯定理
$$P(B_i|A)={P(B_i)P(A|B_i) \over \sum_{j=0}^n P(B_j)P(A|B_j)}$$
而我们知道
$$P(B_i)={1 \over n+1}, \; P(A|B_i)={{i \choose l_1}{n-i \choose l_2} \over {n \choose l}}$$
因此可以计算出$P(B_i|A)$,接下来只要枚举区间即可。

代码

#include <algorithm>
#include <cstdio>
#include <cstring>

static int const N = 55;
double a[N];

double get_c(int n, int m) {
  if (n < m)
    return 0;
  double ret = 1;
  for (int i = 0; i < m; ++i)
    ret *= 1. * (n - i) / (m - i);
  return ret;
}

int main() {
  int n, l1, l2, p;
  scanf("%d%d%d%d", &n, &l1, &l2, &p);
  double b = 0;
  for (int i = 0; i <= n; ++i)
    b += a[i] = 1. / (n + 1) * get_c(i, l1) * get_c(n - i, l2) / get_c(n, l1 + l2);
  for (int i = 1; i <= n + 1; ++i)
    for (int j = 0; j + i - 1 <= n; ++j) {
      double sum = 0;
      for (int k = j; k <= j + i - 1; ++k)
        sum += a[k];
      if (sum / b * 100 + 1e-12 >= p)
        return printf("%d %d\n", j, j + i - 1), 0;
    }
  return 0;
}