题解 CF755G 【PolandBall and Many Other Balls】

· · 题解

更好的体验？

方程为: f_{i,j}=f_{i-1,j-1}+f_{i-2,j-1}+f_{i-1,j} ，其中 f_{i,j} 表示前 i 个球分成 j 组的方案数。

具体就不解释了，过于简单。

然后发现可以NTT， 令 F(x) 为其OGF，即 F_a(x)=\sum\limits_{j=0}^n f_{a,j} x^j

就可以进行多项式加法了，F_n(x)=(1+x)F_{n-1}(x)+xF_{n-2}(x)

现在有三种方法:

  1. 倍增NTT
  2. 容斥卷积
  3. 求特征方程的解

solution 1

观察一下可以发现，如果要合成 f_{a+b,j}

除了上述转移方程以外，还可以 f_{a+b,j}=\sum_{i=1}^jf_{a,i}f_{b,j-i}+\sum_{i=1}^jf_{a-1,i}f_{b-1,j-i-1}

意义描述为两段合并时，中间那两个合不合为一组，状态是等价的。

转化成卷积形式就是

F_{a+b}(x)=F_{a}(x)F_b(x)+xF_{a-1}F_{b-1}

然后转化成

F_{2n}(x)=F^2_{n}(x)+xF^2_{n-1}(x) 之后套倍增模板。 倍增模板实际上就是从高位往低位找'1'，若有，则 $F(n)$ 变成 $F(n+1)$ 。 ```cpp #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<ctime> #include<map> #include<cstdlib> #include<vector> #define gc getchar() #define ll long long #define ull unsigned long long #define file(s) freopen(s".in","r",stdin);freopen(s".out","w",stdout) #define I inline #define clr(f,n) memset(f,0,sizeof(int)*(n)) #define cpy(f,g,n) memcpy(f,g,sizeof(int)*(n)) using namespace std; const int N=2e5+5,mod=998244353,W=mod-1; const ull G=3; template<class o>I void qr(o &x) { char c=gc;int f=1;x=0; while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;} while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;} x*=f; } template<class o>I void qw(o x) { if(x<0)x=-x,putchar('-'); if(x/10)qw(x/10); putchar(x%10+48); } I int pls(int x,int y){return x+=y,x>=mod?x-mod:x;} I int ksm(int a,int b=mod-2){int ans=1;for(;b;b>>=1,a=1ll*a*a%mod)if(b&1)ans=1ll*ans*a%mod;return ans;} int tr[N<<1],cnt; I void rev(int n) { if(cnt==n)return ;cnt=n; for(int i=0;i<n;i++)tr[i]=(tr[i>>1]>>1|((i&1)?n>>1:0)); } void dft(int *g,bool op,int n) { rev(n); static ull f[N<<1],w[N<<1]={1}; for(int i=0;i<n;i++)f[i]=((1ll*mod<<5)+g[tr[i]])%mod; for(int p=2,l=1;p<=n;l=p,p<<=1) { w[1]=ksm(G,op?W-W/p:W/p); for(int i=2;i<l;i++)w[i]=w[i-1]*w[1]%mod; for(int i=0;i<n;i+=p)for(int j=0,t;j<l;j++) t=w[j]*f[i|j|l]%mod,f[i|j|l]=f[i|j]+mod-t,f[i|j]=f[i|j]+t; if(l==(1<<10))for(int i=0;i<n;i++)f[i]%=mod; } if(op)for(int i=0,t=ksm(n);i<n;i++)g[i]=f[i]%mod*t%mod; else for(int i=0;i<n;i++)g[i]=f[i]%mod; } I void px(int *f,int *g,int n){for(int i=0;i<n;i++)f[i]=1ll*f[i]*g[i]%mod;} int f[3][N<<1],g[5][N<<1];//f[0->n],f[1->n-1],f[1->n-2] inline void mul(int m) { int n=1;for(;n<(m<<1);n<<=1); dft(f[0],0,n);dft(f[1],0,n);dft(f[2],0,n); for(int i=0;i<n;i++) g[0][i]=1ll*f[0][i]*f[0][i]%mod,g[1][i]=1ll*f[1][i]*f[1][i]%mod, g[2][i]=1ll*f[0][i]*f[1][i]%mod,g[3][i]=1ll*f[1][i]*f[2][i]%mod, g[4][i]=1ll*f[2][i]*f[2][i]%mod; dft(g[0],1,n),dft(g[1],1,n),dft(g[2],1,n),dft(g[3],1,n),dft(g[4],1,n); f[0][0]=g[0][0];f[1][0]=g[2][0],f[2][0]=g[1][0]; for(int i=1;i<n;i++) f[0][i]=pls(g[0][i],g[1][i-1]), f[1][i]=pls(g[2][i],g[3][i-1]), f[2][i]=pls(g[1][i],g[4][i-1]); clr(g[0],n),clr(g[1],n);clr(g[2],n),clr(g[3],n),clr(g[4],n); clr(f[0]+m,n);clr(f[1]+m,n);clr(f[2]+m,n); } void add(int n) { cpy(f[2],f[1],n);cpy(f[1],f[0],n);clr(f[0],n);f[0][0]=1; for(int i=1;i<n;i++)f[0][i]=(1ll*f[1][i-1]+1ll*f[2][i-1]+1ll*f[1][i])%mod; } int main() { int n,m;qr(n),qr(m);f[0][0]=f[1][0]=f[0][1]=1;int lg=log2(n); for(int i=lg-1;~i;i--) { mul(m+5); if(n&(1<<i))add(m+5); } for(int i=1;i<=m;i++) qw(f[0][i]),putchar(' '); puts(""); return 0; } ``` #### solution 2 考虑枚举有多少个二， 有两种形式: $$\begin{aligned}ans_{i}=\sum_{j=1}^i\dbinom{n-j}{j}\dbinom{n-2j}{i-j}=\sum_{j=1}^i\dbinom{n-j}{i}\dbinom{i}{j}\end{aligned}$$ 第一种就是把 $j$ 个球先拿出来，然后插进 $n-j$ 个空( $n-j+1$ 的同学，最后一个空不要)的方案数,这 $j$ 个球自动与其后面相邻的球合并在一起形成 $j$ 堆。 之后从剩下的 $n-2j$ 个球中选 $i-j$ 个球凑成 $i-j$ 堆。 第二种其实是与第一种等价的。 相当于有一个游戏 $n-j$ 个球，其中有 $i$ 个要拿出来，$i$ 个中有 $j$ 个比较特殊(代表着原来游戏中的两个球)，算出来的方案数就是上第二式。 如果不想这样理解也是可以通过一式转化的。 --- 观察二式，$\sum\limits_{j=0}^i \dbinom{n-j}{i}\dbinom{i}{j}

它还有另外一重意义就是前 i 个选 [0,i] 个，之后任意再选 i 个，球不重复的方案数。

考虑容斥枚举前后两次选择至少有 j 个重复的球，也就是前 i 个至少选 j 个，之后在 n 个中选 i 个，

且已知最少重复 j 个球的方案数。

很显然，方案数无关于选取哪些重复球，仅有关于重复球的数量。

(详情可以参考《组合数学》中的容斥原理)

即:

\sum\limits_{j=0}^i (-1)^j\dbinom{i}{j}\dbinom{n-j}{i-j}2^{i-j}

其中 2^{i-j} 表示前 i 个位置中剩下未钦定的 i-j 个球的方案数。

其实把 \dbinom{n-j}{i-j}2^{i-j} 单独隔离开，然后在前 i 位置枚举 j 个位置a_1,a_2,a_3,a_4,\ldots,a_j ，然后这个特定的序列的方案数其实就为\dbinom{n-j}{i-j}2^{i-j}，由于无关于具体位置，而这样的序列共有 \dbinom{i}{j} 个，于是至少为 j 个重复的球 的方案数就为 \dbinom{i}{j}\dbinom{n-j}{i-j}2^{i-j} 。

然后转换成下降幂就可以NTT了:

\sum\limits_{j=0}^i(-1)^j\frac{i!n^{\underline{i}}}{j!(i-j)!n^{\underline{j}}(i-j)!}2^{i-j}

目前最优解就拿到了。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<ctime>
#include<map>
#include<cstdlib>
#include<vector> 
#define gc getchar()
#define ll long long
#define ull unsigned long long
#define file(s) freopen(s".in","r",stdin);freopen(s".out","w",stdout)
#define I inline 
#define clr(f,n) memset(f,0,sizeof(int)*(n))
#define cpy(f,g,n) memcpy(f,g,sizeof(int)*(n)) 
using namespace std;
const int N=2e5+5,mod=998244353,W=mod-1;
const ull G=3;
template<class o>I void qr(o &x)
{
    char c=gc;int f=1;x=0;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
template<class o>I void qw(o x)
{
    if(x<0)x=-x,putchar('-');
    if(x/10)qw(x/10);
    putchar(x%10+48);
}

I int ksm(int a,int b=mod-2){int ans=1;for(;b;b>>=1,a=1ll*a*a%mod)if(b&1)ans=1ll*ans*a%mod;return ans;}
int tr[N<<1],cnt;
I void rev(int n)
{
    if(cnt==n)return ;cnt=n;
    for(int i=0;i<n;i++)tr[i]=(tr[i>>1]>>1|((i&1)?n>>1:0));
} 
void dft(int *g,bool op,int n)
{
    rev(n);
    static ull f[N<<1],w[N<<1]={1};
    for(int i=0;i<n;i++)f[i]=((1ll*mod<<5)+g[tr[i]])%mod;
    for(int p=2,l=1;p<=n;l=p,p<<=1)
    {
        w[1]=ksm(G,op?W-W/p:W/p);
        for(int i=2;i<l;i++)w[i]=w[i-1]*w[1]%mod;
        for(int i=0;i<n;i+=p)for(int j=0,t;j<l;j++)
            t=w[j]*f[i|j|l]%mod,f[i|j|l]=f[i|j]+mod-t,f[i|j]=f[i|j]+t;
        if(l==(1<<10))for(int i=0;i<n;i++)f[i]%=mod;
    }
    if(op)for(int i=0,t=ksm(n);i<n;i++)g[i]=f[i]%mod*t%mod;
    else for(int i=0;i<n;i++)g[i]=f[i]%mod;
}
I void px(int *f,int *g,int n){for(int i=0;i<n;i++)f[i]=1ll*f[i]*g[i]%mod;}
int dfac[N],fac[N],ifac[N],pw[N],n,k,f[N],g[N];
void init(int m)
{
    ifac[0]=fac[0]=dfac[0]=pw[0]=1;
    for(int i=1;i<=m;i++)fac[i]=1ll*fac[i-1]*i%mod,dfac[i]=1ll*dfac[i-1]*(n-i+1)%mod,pw[i]=pw[i-1]*2%mod;
    ifac[m]=ksm(fac[m]);for(int i=m-1;i;i--)ifac[i]=1ll*ifac[i+1]*(i+1)%mod;
}
int main()
{
    qr(n),qr(k);int m;init(m=min(n,k));
    for(int i=0;i<=m;i++)f[i]=(1ll*ifac[i]*ksm(dfac[i])*((i&1)?-1:1)%mod+mod)%mod,g[i]=1ll*ifac[i]*ifac[i]%mod*pw[i]%mod;
    for(n=1;n<=(m<<1);n<<=1);
    dft(f,0,n);dft(g,0,n);
    px(f,g,n);
    dft(f,1,n);
    for(int i=1;i<=m;i++)qw(1ll*dfac[i]*fac[i]%mod*f[i]%mod),putchar(' ');
    for(int i=m+1;i<=k;i++)putchar('0'),putchar(' ');
    puts(""); 
    return 0;
}

solution3

鰰写的很清楚。