Codeforces 755G 的多项式做法

打这场比赛的时候这个做法就口胡出来了……但是当时没有整理多项式的板子所以没时间写……因此知道有一个好的模板是多么重要。这道题是一个很优秀的多项式操作模板题,包含了逆元、开根、求指数和对数等大部分常见多项式操作。

题目大意

nnn 个球排成一列,定义一组球为一个球或相邻的两个球。每个球最多属于一组球。给出 kkk,要求对于 1≤m≤k1\le m\le k1mk 的每个 mmm,求出从序列中恰好选出 mmm 组球的方案数。答案对 998244353998244353998244353 取模。

题目链接

Codeforces 755G

题解

定义 fi,jf_{i,j}fi,j 为从 iii 个球中恰好选出 jjj 组的方案,则考虑第 iii 个球的分组情况,容易得到

fi,j=fi−1,j+fi−1,j−1+fi−2,j−1f_{i,j}=f_{i-1,j}+f_{i-1,j-1}+f_{i-2,j-1}fi,j=fi1,j+fi1,j1+fi2,j1

其中边界条件为 f0,0=1,f1,0=f1,1=1f_{0, 0}=1,f_{1,0}=f_{1,1}=1f0,0=1,f1,0=f1,1=1

Fn(x)=∑fn,k xkF_n(x)=\sum f_{n,k}\ x^kFn(x)=fn,k xk,则上式等价于

Fn(x)=(1+x)Fn−1(x)+xFn−2(x)F_n(x)=(1+x)F_{n-1}(x)+xF_{n-2}(x)Fn(x)=(1+x)Fn1(x)+xFn2(x)

其中边界条件为 F0(x)=1,F1(x)=1+xF_0(x)=1,F_1(x)=1+xF0(x)=1,F1(x)=1+x

仿照二阶线性递推数列通项公式的推导过程,我们可以猜想Fn(x)F_n(x)Fn(x)具有以下形式:

Fn(x)=C0(x)Λ0(x)n+C1(x)Λ1(x)nF_n(x)=C_0(x)\Lambda_0(x)^n+C_1(x)\Lambda_1(x)^nFn(x)=C0(x)Λ0(x)n+C1(x)Λ1(x)n

其中 C0(x),C1(x)C_0(x),C_1(x)C0(x),C1(x) 为待定幂级数,而 Λ0(x),Λ1(x)\Lambda_0(x),\Lambda_1(x)Λ0(x),Λ1(x) 可由下式确定:

Λ(x)2=(1+x)Λ(x)+x\Lambda(x)^2=(1+x)\Lambda(x)+xΛ(x)2=(1+x)Λ(x)+x

可以得到

Λ0(x)=1+x+1+6x+x22Λ1(x)=1+x1+6x+x22

并利用初始条件解出 C0(x),C1(x)C_0(x),C_1(x)C0(x),C1(x),最终可以得到

Fn(x)=(1+x+1+6x+x22)n+1−(1+x−1+6x+x22)n+11+6x+x2F_n(x)=\frac{\left(\frac{1+x+\sqrt{1+6x+x^2}}{2}\right)^{n+1}-\left(\frac{1+x-\sqrt{1+6x+x^2}}{2}\right)^{n+1}}{\sqrt{1+6x+x^2}}Fn(x)=1+6x+x2(21+x+1+6x+x2)n+1(21+x1+6x+x2)n+1

使用NTT计算 Fn(x)F_n(x)Fn(x) 的前 kkk 项即可。另外可以注意到,当 k>nk > nk>n 时答案为 000,且上式分子的第二项的最低次项次数大于 nnn,因此无需计算这一项。

复杂度O(nlogn)O(n\log n)O(nlogn)

代码

好像因为复杂度比官方题解少一个 log\loglog 所以名次比较靠前呀 755G Ranklist

UPD:听说有人在卡时...我就去换了个新板子... 755G Ranklist new

#include <bits/stdc++.h>
#define debug(x) std::cerr << #x << " = " << (x) << std::endl

typedef long long LL;

const int M = 23, P = ((7 * 17) << M) + 1, G = 3;
const int MAXN = (1 << 18) + 10;
int N = 1 << 16;

inline add(int a, int b) {
    return (a + b) % P;
}

inline sub(int a, int b) {
    return (a - b + P) % P;
}

inline int mul(int a, int b) {
    return (LL)a * (LL)b % P;
}

inline int exp(int a, int b) {
    int ans = 1;
    for (; b; b >>= 1) {
        if (b & 1) ans = mul(ans, a);
        a = mul(a, a);
    }
    return ans;
}

inline int inv(int x) {
    return exp(x, P - 2);
}

int eps[MAXN], ieps[MAXN], temp[5][MAXN];

inline void init() {
    int g = exp(G, (P - 1) / N), ig = inv(g);
    eps[0] = ieps[0] = 1;
    for (int i = 1; i < N; i++) eps[i] = mul(eps[i - 1], ig), ieps[i] = mul(ieps[i - 1], g);
}

inline void trans(int n, int x[], int w[]) {
    for (int i = 0, j = 0; i != n; i++) {
        if (i < j) std::swap(x[i], x[j]);
        for (int l = n >> 1; (j ^= l) < l; l >>= 1);
    }
    for (int i = 2; i <= n; i <<= 1) {
        int l = i >> 1, d = N / i;
        for (int j = 0; j != n; j += i)
            for (int k = 0; k != l; k++) {
                int t = mul(x[j + k + l], w[d * k]);
                x[j + k + l] = sub(x[j + k], t);
                x[j + k] = add(x[j + k], t);
            }
    }
}

inline void dft(int n, int x[]) {
    trans(n, x, eps);
}

inline void idft(int n, int x[]) {
    trans(n, x, ieps);
    for (int i = 0, in = inv(n); i < n; i++) x[i] = mul(x[i], in);
}

inline void inv(int n, int x[], int y[]) {
    int *t = temp[0];
    std::fill(y, y + (n << 1), 0);
    y[0] = inv(x[0]);
    for (int i = 4, j = 2; j <= n; j = i, i <<= 1) {
        std::copy(x, x + j, t);
        std::fill(t + j, t + i, 0);
        dft(i, t);
        dft(i, y);
        for (int k = 0; k < i; k++) y[k] = mul(y[k], sub(2, mul(t[k], y[k])));
        idft(i, y);
        std::fill(y + j, y + i, 0);
    }
}

inline void drv(int n, int x[], int y[]) {
    for (int i = 1; i < n; i++) y[i - 1] = mul(i, x[i]);
    y[n - 1] = 0;
}

inline void itg(int n, int x[], int y[]) {
    for (int i = n - 1; i; i--) y[i] = mul(x[i - 1], inv(i));
    y[0] = 0;
}

inline void ln(int n, int x[], int y[]) {
    int *t = temp[1];
    inv(n, x, y);
    drv(n, x, t);
    std::fill(y + n, y + n + n, 0);
    std::fill(t + n, t + n + n, 0);
    dft(n << 1, y), dft(n << 1, t);
    for (int i = 0; i < (n << 1); i++) y[i] = mul(y[i], t[i]);
    idft(n << 1, y);
    std::fill(y + n, y + n + n, 0);
    itg(n, y, y);
}

inline void exp(int n, int x[], int y[]) {
    int *t = temp[2];
    std::fill(y, y + (n << 1), 0);
    y[0] = 1;
    for (int i = 4, j = 2; j <= n; j = i, i <<= 1) {
        ln(j, y, t);
        t[0] = sub(x[0] + 1, t[0]);
        for (int k = 1; k < j; k++) t[k] = sub(x[k], t[k]);
        std::fill(t + j, t + i, 0);
        dft(i, y), dft(i, t);
        for (int k = 0; k < i; k++) y[k] = mul(y[k], t[k]);
        idft(i, y);
        std::fill(y + j, y + i, 0);
    }
}

const int I2 = inv(2);

inline void sqrt(int n, int x[], int y[]) {
    int *t = temp[3];
    std::fill(y, y + (n << 1), 0);
    y[0] = 1;
    for (int i = 4, j = 2; j <= n; j = i, i <<= 1) {
        inv(j, y, t);
        dft(j, y);
        for (int k = 0; k < j; k++) y[k] = mul(y[k], y[k]);
        idft(j, y);
        for (int k = 0; k < j; k++) y[k] = add(y[k], x[k]);
        dft(i, y), dft(i, t);
        for (int k = 0; k < i; k++) y[k] = mul(y[k], t[k]);
        idft(i, y);
        for (int k = 0; k < j; k++) y[k] = mul(y[k], I2);
        std::fill(y + j, y + i, 0);
    }
}

int f[MAXN] = {1, 6, 1}, g[MAXN], h[MAXN] = {1, 1}, l[MAXN];

int main() {
    init();
    int n = 1 << 15, a = 0, b = 0;
    scanf("%d%d", &a, &b);
    sqrt(n, f, g);
    for (int i = 0; i < n; i++) h[i] = mul(I2, add(h[i], g[i]));
    ln(n, h, l);
    for (int i = 0; i < n; i++) l[i] = mul(a + 1, l[i]);
    exp(n, l, h);
    inv(n, g, l);
    dft(n << 1, h), dft(n << 1, l);
    for (int i = 0; i < (n << 1); i++) h[i] = mul(h[i], l[i]);
    idft(n << 1, h);
    for (int i = 1, t = inv(n << 1); i <= b; i++) printf("%d\n", i <= a ? h[i] : 0);
    return 0;
}

4 thoughts on “Codeforces 755G 的多项式做法

  1. 好板子,抄板子 逃。。。0.0

发表评论

电子邮件地址不会被公开。 必填项已用*标注