CF755G-PolandBall and Many Other Balls【倍增FFT】正题

65 阅读 0 评论 43 点赞

我是靠谱客的博主落后鞋子，最近开发中收集的这篇文章主要介绍CF755G-PolandBall and Many Other Balls【倍增FFT】正题，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

正题

题目链接:https://www.luogu.com.cn/problem/CF755G

题目大意

$n$ 个东西排成一排，每个组可以选择一个单独的物品或者两个连续的物品，一个物品不同同时在两个组里，但是可以不在组里。对于 $i \in [1, k]$ 求分成 $i$ 组的方案数。

$10^9,1leq k<2^{15}$

解题思路

有三种方法。

第一种是倍增 $F F T$ ，设 $f_{i,j}$ 表示到第 $i$ 个物品选了 $j$ 组时的方案数，那么设 $F_n(x)=sum_{i=0}^kf_{n,i}x^i$ 。
考虑把这个 $F$ 分成两半，然后考虑中间的选不选就是
$F_{n+m}(x)=F_{n}(x)F_m(x)+xF_{n-1}(x)F_{m-1}(x)$
我们发现如果需要计算 $F_{2^k}$ ，那么我们就需要维护 $F_{2^{k-1}},F_{2^{k-1}-1},F_{2^{k-1}-2}$ 这三个东西。
但是这三个东西也可以用来计算 $F_{2^k-1},F_{2^k-2}$ ，所以可以维护这三个东西就行倍增。

然后处理的时候同理维护一个 $F_{m}$ 和 $F_{m-1}$ 就好了。

时间复杂度 $O(nlog^2 n)$ ，有点卡常
…

第二种方法是直接组合数学推导。将这个序列提出若干段，每一段之间间隔为 $1$ ，那么只有最末尾的段能够长度为 $2$ 的。
$ans_k=sum_{i=1}^kbinom{n-i}{k}binom{k}{i}$
瓶颈在于后面的 $(i k)$ ，也就是要求前后没有重复，所以我们可以考虑允许重复的容斥
$ans_k=sum_{i=1}^k(-1)^{i}binom{k}{i}binom{n-i}{k-i}2^{k-i}$
$sum_{i=1}^k(-1)^ifrac{k!}{i!(k-i)!}frac{(n-i)!}{(k-i)!(n-k)!}2^{k-i}$
$frac{k!}{(n-k)!}sum_{i=1}^kfrac{(-1)^i(n-i)!}{i!}times frac{2^{k-i}}{(k-i)!^2}$
就可以卷积了，时间复杂度 $O (n lo g n)$
…

第三种方法是特征方程，回到第一个方法的 $F_n(x)$ ，我们有
$f_{i,j}=f_{i-1,j}+f_{i-1,j-1}+f_{i-2,j-1}$
$F_n(x)=(1+x)F_{n-1}(x)+xF_{n-2}(x)$
这是一个二次项的递推式，过程就不在论述了，用特征方程化简可以得到
$F_{n}(x)=frac{(frac{x+1-sqrt {x^2+6x+1}}{2})^{n+1}}{sqrt{x^2+6x+1}}(mod x^{n+1})$
然后上全家桶就好了，时间复杂度也是 $O (n lo g n)$

这里的标程用的是第一种方法。

code

#include<cstdio>
#include<cstring>
#include<algorithm>
#define int long long
using namespace std;
const int N=1<<16,P=998244353;
int n,k,m,r[N],f[3][N],t[3][N],g[2][N];
void fm(int &x){x+=x>>31&P;}
int power(int x,int b){
	int ans=1;
	while(b){
		if(b&1)ans=ans*x%P;
		x=x*x%P;b>>=1;
	}
	return ans;
}
void NTT(int *f,int op){
	for(int i=0;i<n;i++)
		if(i<r[i])swap(f[i],f[r[i]]);
	for(int p=2;p<=n;p<<=1){
		int tmp=power(3,(P-1)/p),len=p>>1;
		if(op==-1)tmp=power(tmp,P-2);
		for(int k=0;k<n;k+=p){
			int buf=1;
			for(int i=k,tt;i<(k|len);i++){
				tt=1ll*buf*f[i|len]%P;
				fm(f[i|len]=f[i]-tt);
				fm(f[i]=f[i]+tt-P);
				buf=1ll*buf*tmp%P;
			}
		}
	}
	if(op==-1){
		int invn=power(n,P-2);
		for(int i=0;i<n;i++)
			f[i]=1ll*f[i]*invn%P;
	}
	return;
}
void print(int x)
{if(x>9)print(x/10);putchar(x%10+'0');return;}
signed main()
{
	scanf("%d%d",&m,&k);k++;n=1;
	while(n<(k*2))n<<=1;
	for(int i=0;i<n;i++)
		r[i]=(r[i>>1]>>1)|((i&1)?(n>>1):0);
	f[0][0]=f[0][1]=f[1][0]=g[0][0]=1;
	for(int d=1;d<=m;d<<=1){
		if(m&d){
			for(int j=0;j<3;j++){
				for(int i=0;i<n;i++)
					t[j][i]=(i<k)?f[j][i]:0;
				NTT(t[j],1);
			}
			NTT(g[0],1);NTT(g[1],1);
			for(int i=0;i<n;i++){
				int b0=g[0][i],b1=g[1][i];
				g[0][i]=1ll*b0*t[0][i]%P;
				g[1][i]=1ll*b0*t[1][i]%P;
				t[0][i]=1ll*t[1][i]*b1%P;
				t[1][i]=1ll*t[2][i]*b1%P;
			}
			NTT(g[0],-1);NTT(g[1],-1);
			NTT(t[0],-1);NTT(t[1],-1);
			for(int i=0;i<k-1;i++)
				(g[0][i+1]+=t[0][i])%=P,
				(g[1][i+1]+=t[1][i])%=P;
			for(int i=k;i<n;i++)g[0][i]=g[1][i]=0;
		}
		if(d*2>m)break;
		for(int j=0;j<3;j++){
			for(int i=0;i<n;i++)
				t[j][i]=(i<k)?f[j][i]:0;
			NTT(t[j],1);
		}
		for(int i=0;i<n;i++){
			f[0][i]=1ll*t[0][i]*t[0][i]%P;
			f[1][i]=1ll*t[1][i]*t[0][i]%P;
			f[2][i]=1ll*t[1][i]*t[1][i]%P;
			t[0][i]=1ll*t[1][i]*t[1][i]%P;
			t[1][i]=1ll*t[1][i]*t[2][i]%P;
			t[2][i]=1ll*t[2][i]*t[2][i]%P;
		}
		for(int j=0;j<3;j++)
			NTT(f[j],-1),NTT(t[j],-1);
		for(int i=0;i<k-1;i++)
			(f[0][i+1]+=t[0][i])%P,
			(f[1][i+1]+=t[1][i])%P,
			(f[2][i+1]+=t[2][i])%P;
		for(int i=k;i<n;i++)f[0][i]=f[1][i]=f[2][i]=0;
	}
	for(int i=1;i<k;i++)
		print(g[0][i]),putchar(' ');
	return 0;
}