题解归档 - cf755G

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf755G
• 本地来源：problems/cf755G/idea.md
• 题目链接：https://codeforces.com/contest/755/problem/G
• 原始标题：cf755G — PolandBall and Many Other Balls

思路

cf755G — PolandBall and Many Other Balls

题意

(n) 个球排成一行。选恰好 (m) 个组，每组为单个球或相邻两球；每个球至多属于一组（可不选）。对 (m=1..k) 求方案数，模 (998244353)。(n\le10^9,\ k<2^{15})。

DP

(f(i,j))：考虑前 (i) 个球、恰好 (j) 组的方案数。

[
f(i,j)=f(i-1,j)+f(i-1,j-1)+f(i-2,j-1)
]

初值 (f(0,0)=1)，(f(1,0)=f(1,1)=1)。

大 (n)：生成函数 + 矩阵快速幂

令 (F_i(z)=\sum_j f(i,j)z^j)，则

[
F_{i+1}(z)=(1+z)F_i(z)+zF_{i-1}(z)
]

即向量 ((F_i,F_{i-1})^\top) 左乘 (2\times2) 多项式矩阵 (\begin{pmatrix}1+z & z\ 1 & 0\end{pmatrix})。

• 初值：(F_0=1,\ F_1=1+z)。
• 答案：(F_n) 中 (z^m) 的系数，(m=1..k)。
• 多项式乘法用 NTT，矩阵幂 (O(k\log k\log n))。

样例

(n=3,k=3)：(m=1) 时 5 种（3 个单球 + 2 个相邻对）；(m=2) 时 5 种；(m=3) 时 1 种。输出 5 5 1。

代码

来源：problems/cf755G/solution.cpp

/* Author: likely
 * Time: 2026-06-08 04:00:43
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod=998244353,G=3;
const ll maxk=1<<15;
ll NTT_R[maxk*4+5],buf1[maxk*4+5],buf2[maxk*4+5],L=0,limit=1;
ll qmksm(ll a,ll b){
    ll sc=1;
    while(b>0){
        if(b&1) sc=(sc*a)%mod;
        a=(a*a)%mod,b>>=1;
    }
    return sc%mod;
}
ll ny(ll x){
    return qmksm(x,mod-2);
}
void NTT(ll a[],ll type){
    ll i,j,k,mid,wn,len,pos,w,x,y;
    for(i=0;i<limit;i++) if(i<NTT_R[i]) swap(a[i],a[NTT_R[i]]);
    for(mid=1;mid<limit;mid<<=1){
        wn=qmksm(G,(mod-1)/(mid*2));
        if(type==-1) wn=qmksm(wn,mod-2);
        for(len=mid<<1,pos=0;pos<limit;pos+=len){
            for(k=0,w=1;k<mid;k++,w=(w*wn)%mod){
                x=a[pos+k],y=(w*a[pos+mid+k])%mod;
                a[pos+k]=(x+y)%mod,a[pos+k+mid]=(x-y+mod)%mod;
            }
        }
    }
    if(type==-1){
        ll inv=ny(limit);
        for(i=0;i<limit;i++) a[i]=(a[i]*inv)%mod;
    }
}
void pmul(ll A[],ll B[],ll C[],ll lim){
    ll i,deg=0;
    for(i=0;i<=lim;i++) if(A[i] or B[i]) deg=max(deg,i);
    deg=min(deg*2,lim*2);
    for(limit=1,L=0;limit<=deg;limit<<=1) L++;
    for(i=0;i<limit;i++) NTT_R[i]=(NTT_R[i>>1]>>1)|((i&1)<<(L-1));
    for(i=0;i<limit;i++) buf1[i]=buf2[i]=0;
    for(i=0;i<=lim;i++){
        buf1[i]=(A[i]%mod+mod)%mod;
        buf2[i]=(B[i]%mod+mod)%mod;
    }
    NTT(buf1,1),NTT(buf2,1);
    for(i=0;i<limit;i++) buf1[i]=(buf1[i]*buf2[i])%mod;
    NTT(buf1,-1);
    for(i=0;i<=lim;i++) C[i]=buf1[i];
    for(i=lim+1;i<=deg;i++) C[i]=0;
}
ll pa[maxk+5],pb[maxk+5],pc[maxk+5],pd[maxk+5];
ll ma[2][2][maxk+5],mb[2][2][maxk+5],mc[2][2][maxk+5],mres[2][2][maxk+5],mbase[2][2][maxk+5];
void padd(ll a[],ll b[],ll c[],ll lim){
    ll i;
    for(i=0;i<=lim;i++) c[i]=(a[i]+b[i])%mod;
}
void mat_mul(ll A[2][2][maxk+5],ll B[2][2][maxk+5],ll C[2][2][maxk+5],ll lim){
    ll i,j,t;
    for(i=0;i<2;i++) for(j=0;j<2;j++){
        for(t=0;t<=lim;t++) pc[t]=0;
        for(t=0;t<2;t++){
            pmul(A[i][t],B[t][j],pd,lim);
            padd(pc,pd,pc,lim);
        }
        for(t=0;t<=lim;t++) C[i][j][t]=pc[t];
    }
}
void mat_copy(ll A[2][2][maxk+5],ll B[2][2][maxk+5],ll lim){
    ll i,j,t;
    for(i=0;i<2;i++) for(j=0;j<2;j++) for(t=0;t<=lim;t++) B[i][j][t]=A[i][j][t];
}
void mat_pow(ll M[2][2][maxk+5],ll e,ll R[2][2][maxk+5],ll lim){
    ll i,j,t;
    mat_copy(M,mbase,lim);
    for(i=0;i<2;i++) for(j=0;j<2;j++) for(t=0;t<=lim;t++) mres[i][j][t]=0;
    mres[0][0][0]=1,mres[1][1][0]=1;
    while(e>0){
        if(e&1){
            mat_mul(mres,mbase,mc,lim);
            mat_copy(mc,mres,lim);
        }
        mat_mul(mbase,mbase,mc,lim);
        mat_copy(mc,mbase,lim);
        e>>=1;
    }
    mat_copy(mres,R,lim);
}
int main(){
    ll n,k,i,j,m;
    cin>>n>>k;
    for(i=0;i<=k;i++){
        ma[0][0][i]=ma[0][1][i]=ma[1][0][i]=ma[1][1][i]=0;
    }
    ma[0][0][0]=1,ma[0][0][1]=1;
    ma[0][1][1]=1;
    ma[1][0][0]=1;
    pa[0]=1,pa[1]=1;
    pb[0]=1;
    if(n==1){
        for(m=1;m<=k;m++){
            if(m>1) cout<<" ";
            cout<<(m<=1?1:0);
        }
        cout<<"\n";
        return 0;
    }
    mat_pow(ma,n-1,mb,k);
    for(i=0;i<=k;i++) pc[i]=pd[i]=0;
    pmul(mb[0][0],pa,pc,k);
    pmul(mb[0][1],pb,pd,k);
    padd(pc,pd,pc,k);
    for(m=1;m<=k;m++){
        if(m>1) cout<<" ";
        cout<<(pc[m]%mod+mod)%mod;
    }
    cout<<"\n";
    return 0;
}