[题解] LuoguP3321 [SDOI2015]序列统计

感觉这个题挺妙的......

考虑最暴力的\(dp\)，令\(f[i][j]\)表示生成大小为\(i\)的序列，积为\(j\)的方案数，这样做是\(O(nm)\)的。

转移就是

\[f[i+1][j] = \sum\limits_{ab\equiv j(mod\ m)} f[i][a]f[1][b]
\]

后面那个柿子很像卷积？但下标是乘法......好像不那么好卷。

套路的去个对数啥的把他转化成加法？比方说取个ln

那底数怎么确定呢？

我们想把\(1...m-1\)这\(m-1\)个数通过取对数的方法映射到\(0,1,...m-2\)这些不同的数上。

咋办？以原根为底就好辣！（下面默认\(m\)原根是\(g\)，\(\log a = \log_{g} a\)）。

因为根据定义我们知道\(g^{m-1} \equiv 1\ (mod \ m)\)，且\(g^0,g^1,\cdots,g^{m-2}\)是\(m-1\)个不同的数。

所以在上面的\(dp\)转移中，我们令\(A = \log a, B = \log b, C = \log j\)，然后再改一下状态，转移就变成了

\[f[i+1][C] = \sum\limits_{A+B=C} f[i][A]f[1][B]
\]

这样一阶段的转移就是卷积的形式，且转移方式是相同的。

但是\(n\)很大.......因为转移的特殊性，我们可以类似快速幂那样倍增（有点像矩乘？）

具体边界还有一些要注意的地方就看代码吧：

#include <bits/stdc++.h>

using namespace std;

const int N=20100,P=1004535809,gen=3,igen=334845270;

inline int add(int x,int y,int mod=P){

	return x+y>=mod?x+y-mod:x+y;

}

inline int sub(int x,int y,int mod=P){

	return x-y<0?x-y+mod:x-y;

}

inline int fpow(int x,int y,int mod=P){

	int ret=1; for(x%=mod;y;y>>=1,x=1ll*x*x%mod)

		if(y&1) ret=1ll*ret*x%mod;

	return ret;

}

int rev[N];

void init(int n){

	for(int i=0;i<n;i++)

		rev[i]=rev[i>>1]>>1|((i&1)?n>>1:0);

}

void ntt(int *f,int n,int flg){

	for(int i=0;i<n;i++) if(rev[i]<i) swap(f[i],f[rev[i]]);

	for(int len=2,k=1;len<=n;len<<=1,k<<=1){

		int wn=fpow(flg==1?gen:igen,(P-1)/len);

		for(int i=0;i<n;i+=len){

			for(int w=1,j=i;j<i+k;j++,w=1ll*w*wn%P){

				int tmp=1ll*f[j+k]*w%P;

				f[j+k]=sub(f[j],tmp),f[j]=add(f[j],tmp);

			}

		}

	}

	if(flg==-1){

		int inv=fpow(n,P-2);

		for(int i=0;i<n;i++) f[i]=1ll*f[i]*inv%P;

	}

}

int limit,m,n,X,C;

void mult(int *f,int *g){

	static int F[N],G[N];

	for(int i=0;i<m-1;i++) F[i]=f[i],G[i]=g[i];

	for(int i=m-1;i<limit;i++) F[i]=G[i]=0;

	ntt(F,limit,1),ntt(G,limit,1);

	for(int i=0;i<limit;i++) F[i]=1ll*F[i]*G[i]%P;

	ntt(F,limit,-1);

	for(int i=0;i<m-1;i++) f[i]=add(F[i],F[i+m-1]); // 这里挺重要的qwq，因为卷起来后次数是2(m-1)的，又因为m-1一个循环，要加上去

}

int chk(int g){

	for(int i=2;i*i<=m-1;i++)

		if((m-1)%i==0&&(fpow(g,i,m)==1||fpow(g,(m-1)/i,m)==1)) return 0;

	return 1;

}

int getG(){

	for(int i=2;;i++) if(chk(i))return i;

}

map<int,int> id;

void getans(int *f,int n,int *ans){

	for(ans[id[1]]=1;n;n>>=1,mult(f,f)) // 一开始的时候只有f[0][1]是1

		if(n&1) mult(ans,f);

}

int f[N],ans[N];

int main(){

	scanf("%d%d%d%d",&n,&m,&X,&C);

	limit=1; while(limit<=m*2)limit<<=1; init(limit);

	int g=getG(); // m的原根

	for(int i=0;i<m-1;i++)id[fpow(g,i,m)]=i;

	for(int i=1;i<=C;i++){

		int x; scanf("%d",&x),x%=m;

		if(x) f[id[x]]=1;

	}

	getans(f,n,ans);

	printf("%d\n",ans[id[X]]);

	return 0;

}

巴特西

[题解] LuoguP3321 [SDOI2015]序列统计

最新文章

热门文章