[cpp] /* 注意dp的for循環，狀態之間的重復計算 dp[i][j]表示i種不同的余數的和為j的方法樹 */ #include<stdio.h> #include<string.h> typedef long long lld; const int mod=1000000007; lld dp[52][1300]; lld fac[52]; class DistinctRemainders{ public: lld Bin(lld a,lld b){ lld ret=1; while(b){ if(b&1)ret=ret*a%mod; b>>=1; a=a*a%mod; } return ret; } void init(int M){ memset(fac,0,sizeof(fac)); fac[0]=1; for(int i=1;i<=M;i++) fac[i]=fac[i-1]*i%mod; } lld Kao(lld x,lld y){ lld ret=1; for(lld i=1;i<=y;i++){ ret=ret*x%mod; x--; } return ret; } lld Gao(lld x,lld y){ return Kao(y,x)*Bin(Kao(x,x),mod-2)%mod; } int howMany(lld N, int M){ int i,j,k; init(M); memset(dp,0,sizeof(dp)); dp[0][0]=1; for(i=0;i<M;i++){ for(j=M;j>0;j--){ for(k=M*M/2;k>=i;k--){ if(!dp[j-1][k-i])continue; dp[j][k]=(dp[j-1][k-i]+dp[j][k])%mod; // printf("dp[%d][%d]=%lld \n",i,j,dp[i][j]); } } } lld ans=0; for(i=1;i<=M;i++){ for(j=0;j<=M*M/2;j++){ if(!dp[i][j])continue; if(j>N || (N-j)%M!=0)continue; ans=(ans+(dp[i][j]*fac[i]%mod)*Gao(i-1,(N-j)/M%mod+i-1))%mod; printf("i==%d j==%d %lld \n",i,j,ans); } } return (int)ans; } };
