「CF755G」PolandBall and Many Other Balls

发表于 更新于 分类于

题目链接：https://codeforces.com/problemset/problem/755/G。

计数题。大力出奇迹。

最近写了好多题都没写题解，这个题好像题解很好写 就来写一写

考虑$dp$，$f_{i,j}$表示前$i$个位置填了$j$个，转移：

对于一个固定的$i$，可以写成生成函数$F_i(x)=\sum f_{i,j}x^j$。

转移就是：

这东西长得和斐波那契一样，类似的有两种优化方法。

第一种很显然，我们写成矩阵的形式：

这时候，只需要有坚定的信仰，大力出奇迹，就能巨大常数$O(n\log ^2 n)​$干过去了，代码在下面。

当然也可以通过特征方程找出通解：

特征方程就是$z^2=(1+x)z+x$，解出来就是：

后面的都一样：

很简单可以解出$a,b$，那么通式就是：

利用多项式开根和求逆可以求出上面的所有参数，利用多项式$\ln,\exp$可以快速计算，复杂度$O(n\log n)$。感兴趣的同学自行实现好了，我太懒了不想写了

矩阵代码：（注意下这份代码由于在函数里面开了太大内存，不开栈运行不了我找了好久才发现是这个原因，一开始都不能读入）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include<bits/stdc++.h>
using namespace std;

void read(int &x) {
    x=0;int f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}

void print(int x) {
    if(x<0) putchar('-'),x=-x;
    if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}

#define lf double
#define ll long long 

#define pii pair<int,int >
#define vec vector<int >

#define pb push_back
#define mp make_pair
#define fr first
#define sc second

#define FOR(i,l,r) for(int i=l,i##_r=r;i<=i##_r;i++)

const int maxn = 7e4+10;
const int inf = 1e9;
const lf eps = 1e-8;
const int mod = 998244353;

int w[maxn],pos[maxn],N=maxn-1,bit,n,k;

int qpow(int a,int x) {
    int res=1;
    for(;x;x>>=1,a=1ll*a*a%mod) if(x&1) res=1ll*res*a%mod;
    return res;
}

void init() {
    for(N=1,bit=-1;N<=k<<1;N<<=1,bit++);
    for(int i=1;i<=N;i++) pos[i]=pos[i>>1]>>1|((i&1)<<bit);
    w[0]=1,w[1]=qpow(3,(mod-1)/N);
    for(int i=2;i<=N;i++) w[i]=1ll*w[i-1]*w[1]%mod;
}

struct poly {
    int r[maxn];

    poly () {for(int i=0;i<N;i++) r[i]=0;}

    void ntt(int op) {
        for(int i=1;i<N;i++) if(pos[i]>i) swap(r[i],r[pos[i]]);
        for(int i=1,d=N>>1;i<N;i<<=1,d>>=1)
            for(int j=0;j<N;j+=i<<1)
                for(int k=0;k<i;k++) {
                    int x=r[j+k],y=1ll*w[k*d]*r[i+j+k]%mod;
                    r[j+k]=(x+y)%mod,r[i+j+k]=(x-y+mod)%mod;
                }
        if(op==-1) {
            int d=qpow(N,mod-2);reverse(r+1,r+N);
            for(int i=0;i<=k;i++) r[i]=1ll*r[i]*d%mod;
            for(int i=k+1;i<N;i++) r[i]=0;
        }
    }

    poly operator + (poly a) const {
        for(int i=0;i<N;i++) a.r[i]=(a.r[i]+r[i])%mod;
        return a;
    }
    
    poly operator * (poly a) const {
        for(int i=0;i<N;i++) a.r[i]=1ll*a.r[i]*r[i]%mod;
        return a;
    }
};

struct matrix {
    poly a[2][2];

    poly* operator [] (const int &x) {return a[x];}

    matrix operator * (matrix c) const {
        matrix res,b=*this;
        for(int i=0;i<2;i++)
            for(int j=0;j<2;j++) b[i][j].ntt(1),c[i][j].ntt(1);
        for(int i=0;i<2;i++)
            for(int j=0;j<2;j++)
                for(int k=0;k<2;k++)
                    res[i][j]=res[i][j]+b[i][k]*c[k][j];
        for(int i=0;i<2;i++)
            for(int j=0;j<2;j++) res[i][j].ntt(-1);
        return res;
    }

    matrix operator ^ (int x) const {
        matrix b=*this,res;res.a[0][0].r[0]=res.a[1][1].r[0]=1;
        for(;x;x>>=1,b=b*b) if(x&1) res=res*b;
        return res;
    }
}st,tr;

int main() {
    read(n),read(k);init();
    st.a[0][0].r[0]=st.a[0][0].r[1]=st.a[0][1].r[0]=1;
    tr.a[0][0]=st.a[0][0];
    tr.a[1][0].r[1]=1;
    tr.a[0][1].r[0]=1;
    st=st*(tr^(n-1));
    for(int i=1;i<=k;i++) printf("%d ",st.a[0][0].r[i]);puts("");
    return 0;
}