题面

传送门

思路

首先，这个数据如果没有这么大，我们还是可以做朋友的......

设$dp\left[i\right]\left[j\right]$代表前j个零食分给了前i个人的方案数

那么dp方程显然：

$dp\left[i\right]\left[j\right]=\sum_{k=1}^{j-1} dp\left[i-1\right]\left[k\right]+f\left(j-k\right)$

其中$f\left(x\right)$就是题目里给的那个二次函数

同时有一个性质：

$dp\left[i\right]\left[j\right]=dp\left[\frac i2\right]\left[k\right]\ast dp\left[\frac i2\right]\left[j-k\right]$

显然这道题不能直接O(nm)递推......那我们换个办法来想

n辣么大，为什么我们不考虑一下用倍增的方法呢？正好上面那个性质可以利用一下

并且还应当注意，我们最后要求的是$\sum_{i=1}^n dp\left[i\right]\left[m\right]$

所以我们设$p\left[i\right]\left[j\right]=\sum_{k=1}^n dp\left[k\right]\left[j\right]$

$p\left[i\right]\left[j\right]=p\left[\frac i2\right]\left[j\right]+\sum_{k=1}^{\frac i2}dp\left[k+\frac i2\right]\left[j\right]$

$p\left[i\right]\left[j\right]=p\left[\frac i2\right]\left[j\right]+\sum_{k=1}^{\frac i2}\sum_{l=1}^{j-1}dp\left[k\right]\left[l\right]dp\left[\frac i2\right]\left[j-l\right]$

$p\left[i\right]\left[j\right]=p\left[\frac i2\right]\left[j\right]+\sum_{l=1}^{{j-1}\sum_{k=1}}{\frac i2}dp\left[k\right]\left[l\right]dp\left[\frac i2\right]\left[j-l\right]$

$p\left[i\right]\left[j\right]=p\left[\frac i2\right]\left[j\right]+\sum_{l=1}^{j-1}dp\left[\frac i2\right]\left[j-l\right]\sum_{k=1}^{\frac i2}dp\left[k\right]\left[l\right]$

$p\left[i\right]\left[j\right]=p\left[\frac i2\right]\left[j\right]+\sum_{l=1}^{j-1}dp\left[\frac i2\right]\left[j-l\right]p\left[\frac i2\right]\left[l\right]$

也就是说p可以由上一层的p加上一层的dp与p的卷积得到，而dp可以由上一层的dp自乘得到

那么自然可以用倍增p的第一层参数的方法，用FFT优化一下，一直做到n

时间效率为$O\left(mlogmlogn\right)$

注意：将n转化为二进制，那么为一的那些位，要在倍增完以后再推一层

Code：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

using namespace std;

inline int read(){

	int re=0,flag=1;char ch=getchar();

	while(ch>'9'||ch<'0'){

		if(ch=='-') flag=-1;

		ch=getchar();

	}

	while(ch>='0'&&ch<='9') re=(re<<1)+(re<<3)+ch-'0',ch=getchar();

	return re*flag;

}

struct complex{

	double x,y;

	complex(double xx=0,double yy=0){x=xx;y=yy;}

	complex operator +(const complex &b){return complex(x+b.x,y+b.y);}

	complex operator -(const complex &b){return complex(x-b.x,y-b.y);}

	complex operator *(const complex &b){return complex(x*b.x-y*b.y,x*b.y+y*b.x);}

}A[100010],B[100010];

const double pi=acos(-1.0);

int n,m,limit=1,cnt=0,r[100010];

int MOD;

void fft(complex *a,double type){

	int i,j,k,mid;complex x,y,wn,w;

	for(i=0;i<limit;i++) if(i<r[i]) swap(a[i],a[r[i]]);

	for(mid=1;mid<limit;mid<<=1ll){

		wn=complex(cos(pi/mid),type*sin(pi/mid));

		for(j=0;j<limit;j+=(mid<<1ll)){

			w=complex(1,0);

			for(k=0;k<mid;k++,w=w*wn){

				x=a[j+k];y=a[j+k+mid]*w;

				a[j+k]=x+y;a[j+k+mid]=x-y;

			}

		}

	}

}

int now=1,w=0,g[100010]={0},p[100010]={0},f[100010]={0};

int a1,a2,a3;

void solve1(){

	int i;

	for(i=0;i<=limit;i++) A[i]=B[i]=complex(0,0);

	for(i=0;i<=limit;i++) A[i].x=p[i],B[i].x=g[i];

	fft(A,1);fft(B,1);

	for(i=0;i<=limit;i++) A[i]=A[i]*B[i];

	fft(A,-1);

	for(i=1;i<=m;i++) p[i]=(p[i]+(int)(A[i].x/limit+0.5)%MOD)%MOD;

	for(i=0;i<=limit;i++) A[i]=complex(0,0);

	for(i=0;i<=limit;i++) A[i].x=g[i];

	fft(A,1);

	for(i=0;i<=limit;i++) A[i]=A[i]*A[i];

	fft(A,-1);

	for(i=1;i<=m;i++) g[i]=(int)(A[i].x/limit+0.5)%MOD;

}

void solve2(){

	int i;

	for(i=0;i<=limit;i++) A[i]=B[i]=complex(0,0);

	for(i=1;i<=m;i++) A[i].x=f[i],B[i].x=g[i];

	fft(A,1);fft(B,1);

	for(i=0;i<=limit;i++) A[i]=A[i]*B[i];

	fft(A,-1);

	for(i=1;i<=m;i++) g[i]=(int)(A[i].x/limit+0.5)%MOD,p[i]=(p[i]+g[i])%MOD;

}

int main(){

	m=read();MOD=read();n=read();a1=read();a2=read();a3=read();

	int i;

	a1%=MOD;a2%=MOD;a3%=MOD;

	for(i=1;i<=m;i++) g[i]=p[i]=f[i]=((((((a1*i)%MOD)*i)%MOD)+a2*i%MOD)+a3)%MOD;

	while(limit<=(m<<1ll)) limit<<=1ll,cnt++;

	for(i=0;i<limit;i++) r[i]=((r[i>>1ll]>>1ll)|((i&1ll)<<(cnt-1ll)));

	while((now<<1ll)<=n) now<<=1ll,w++;

	while(w){

		w--;

		solve1();//倍增

		if(n&(1<<w)) solve2();//这一位应该是个奇数的，再推一层

	}

	printf("%lld\n",p[m]%MOD);

}

巴特西

[JSOI2012][bzoj4332] 分零食 [FFT]

题面

思路

$dp\left[i\right]\left[j\right]=\sum_{k=1}^{j-1} dp\left[i-1\right]\left[k\right]+f\left(j-k\right)$

$dp\left[i\right]\left[j\right]=dp\left[\frac i2\right]\left[k\right]\ast dp\left[\frac i2\right]\left[j-k\right]$

$p\left[i\right]\left[j\right]=p\left[\frac i2\right]\left[j\right]+\sum_{k=1}^{\frac i2}dp\left[k+\frac i2\right]\left[j\right]$

$p\left[i\right]\left[j\right]=p\left[\frac i2\right]\left[j\right]+\sum_{k=1}^{\frac i2}\sum_{l=1}^{j-1}dp\left[k\right]\left[l\right]dp\left[\frac i2\right]\left[j-l\right]$

$p\left[i\right]\left[j\right]=p\left[\frac i2\right]\left[j\right]+\sum_{l=1}^{{j-1}\sum_{k=1}}{\frac i2}dp\left[k\right]\left[l\right]dp\left[\frac i2\right]\left[j-l\right]$

$p\left[i\right]\left[j\right]=p\left[\frac i2\right]\left[j\right]+\sum_{l=1}^{j-1}dp\left[\frac i2\right]\left[j-l\right]\sum_{k=1}^{\frac i2}dp\left[k\right]\left[l\right]$

$p\left[i\right]\left[j\right]=p\left[\frac i2\right]\left[j\right]+\sum_{l=1}^{j-1}dp\left[\frac i2\right]\left[j-l\right]p\left[\frac i2\right]\left[l\right]$

Code：

最新文章

热门文章

巴特西

[JSOI2012][bzoj4332] 分零食 [FFT]

题面

思路

$dp\left[i\right]\left[j\right]=\sum_{k=1}^{j-1} dp\left[i-1\right]\left[k\right]+f\left(j-k\right)$

$dp\left[i\right]\left[j\right]=dp\left[\frac i2\right]\left[k\right]\ast dp\left[\frac i2\right]\left[j-k\right]$

$p\left[i\right]\left[j\right]=p\left[\frac i2\right]\left[j\right]+\sum_{k=1}^{\frac i2}dp\left[k+\frac i2\right]\left[j\right]$

$p\left[i\right]\left[j\right]=p\left[\frac i2\right]\left[j\right]+\sum_{k=1}^{\frac i2}\sum_{l=1}^{j-1}dp\left[k\right]\left[l\right]dp\left[\frac i2\right]\left[j-l\right]$

$p\left[i\right]\left[j\right]=p\left[\frac i2\right]\left[j\right]+\sum_{l=1}{j-1}\sum_{k=1}{\frac i2}dp\left[k\right]\left[l\right]dp\left[\frac i2\right]\left[j-l\right]$

$p\left[i\right]\left[j\right]=p\left[\frac i2\right]\left[j\right]+\sum_{l=1}^{j-1}dp\left[\frac i2\right]\left[j-l\right]\sum_{k=1}^{\frac i2}dp\left[k\right]\left[l\right]$

$p\left[i\right]\left[j\right]=p\left[\frac i2\right]\left[j\right]+\sum_{l=1}^{j-1}dp\left[\frac i2\right]\left[j-l\right]p\left[\frac i2\right]\left[l\right]$

Code：

最新文章

热门文章

$p\left[i\right]\left[j\right]=p\left[\frac i2\right]\left[j\right]+\sum_{l=1}^{{j-1}\sum_{k=1}}{\frac i2}dp\left[k\right]\left[l\right]dp\left[\frac i2\right]\left[j-l\right]$