题目大意
给定数n、m,求有多少个序列{Ai}满足 (∑Ai)=n 且Aimod m互不相同,方案数对905 229 641取mod(顺序不同,也算不同方案)
首先对于序列{Ai}我们可以枚举里面的元素个数,然后按顺序处理放什么元素进去(从小到大),对于元素,方便起见,我们先只考虑0~m-1。(其余的我们可以在后面用挡板问题将多余的m放进去,由于允许顺序不同,后面乘个阶乘就可以了)
这样我们可以得出一个dp方程:
设fi,j,k为做到元素i(可选可不选),用了j个数,和为k的方案数。(转移的话手动推一下就出来了)
难点在于n比较大,组合数里不能预处理出来,而mod的数也比较大,不能用羞涩的老鼠定理,然而我们发现m比较小,分子部分只有100个数乘起来,暴力即可。
贴代码
#include<cstdio>#include<algorithm>#include<iostream>#include<cmath>#define MOD 905229641using namespace std;#define N 101long long n;int m,ans;int f[2][N][N][N],a[N],ni[N];void init(){ scanf("%lld %d",&n,&m);}int calc(int x,int y){ if (!y)return 1; static int s; s=calc(x,y/2); s=(long long)s*s%MOD; return (y&1)?(long long)s*x%MOD:s;}void pre(){ a[1]=1; for (int i=2;i<=m;i++) a[i]=(long long)a[i-1]*i%MOD; ni[m]=calc(a[m],MOD-2); for (int i=m-1;i;i--) ni[i]=(long long)ni[i+1]*(i+1)%MOD;}int C(long long x,int y){ if (y==x||!y)return 1; static int s; s=ni[y]; for (int i=0;i<y;i++) s=(long long)s*((x-i)%MOD)%MOD; return s;}void work(){ static int bz,bz1,x,y; static long long s; f[0][0][0][0]=1,bz=0,bz1=1; for (int i=0;i<m;i++,bz^=1,bz1^=1){ for (int j=0;j<=m;j++) for (int k=0;k<=m;k++) for (int l=0;l<=m;l++) f[bz1][j][k][l]=f[bz][j][k][l]; for (int j=0;j<m;j++) for (int k=0;k<=m;k++) for (int l=0;l<=m;l++) if (f[bz][j][k][l]){ y=(l+i)/m; x=(l+i)%m; f[bz1][j+1][k+y][x]=(f[bz1][j+1][k+y][x]+f[bz][j][k][l])%MOD; } } x=n%m; s=n/m; if (s<m)y=s; else y=m; for (int i=1;i<=m;i++) for (int j=y;j>=0;j--) if (f[bz][i][j][x]) if (i==1)ans=(ans+f[bz][i][j][x])%MOD; else ans=(ans+(long long)f[bz][i][j][x]*C(s-j+i-1,i-1)%MOD*a[i]%MOD)%MOD;}void write(){ printf("%d",ans);}int main(){ init(); pre(); work(); write(); return 0;}