经典题|3462: DZY Loves Math II 经典题|dp

一开始看到这题忽视了S以及问题的特殊性；从而想到了奇怪的方向
注意到构成元素均为S的约数，所以划分n的方案可以分成若干S的和与零散部分；
其中零散部分必不能再拆出S，否则会重复计算；
如此，使用组合数与多重背包即可；

#include #define rep(i,k,n) for(int i=k; i<=n; i++) #define rep2(i,k,n) for(int i=k; i>=n; i--) using namespace std; typedef long long ll; const int mod=1e9+7; const int N=2e7+7; void upd(int& x,int y){x+=y; if(x>=mod)x-=mod; while(x<0)x+=mod; } void upd(ll& x,int y){x+=y; if(x>=mod)x-=mod; while(x<0)x+=mod; } int qpow(int a,int b){ int aa=a,res=1; for(; b; b>>=1){if(b&1)res=1ll*res*aa%mod; aa=1ll*aa*aa%mod; }return res; } ll n,part,once=0; int S,q,a[10],cnt=0,pin[10],f[N],sum[N],last[N],yv; void Bag(){ f[0]=1; rep(i,1,cnt){ memcpy(last,f,sizeof(int)*(S*(i-1)+13)); rep(j,0,a[i]-1)sum[j]=f[j]; rep(s,a[i],i*S){ int j=s%a[i]; if(s>=S)upd(sum[j],-last[s-S]); upd(sum[j],last[s]); f[s]=sum[j]; } } } int ch(ll x,int y){ x=x+y-1,y--; x%=mod; int res=1; rep(i,0,y-1){res=1ll*res*x%mod; upd(x,-1); } res=1ll*res*pin[y]%mod; return res; } int main(){ scanf("%d%d",&S,&q); int cs=S; int lim=sqrt(S)+1; rep(i,2,lim)if(cs%i==0){ a[++cnt]=i; cs/=i; once+=i; if(cs%i==0){while(q--)puts("0"); return 0; } } if(cs!=1)a[++cnt]=cs,once+=cs; pin[0]=1; rep(i,1,7)pin[i]=pin[i-1]*i; rep(i,1,7)pin[i]=qpow(pin[i],mod-2); Bag(); while(q--){ scanf("%lld",&n); n-=1ll*once; if(n<0){puts("0"); continue; } part=n/S,yv=n%S; int ans=0; rep(i,0,cnt-1){ if(yv+1ll*i*S>n)break; upd(ans,1ll*f[yv+i*S]*ch(part-i,cnt)%mod); } upd(ans,0); printf("%d\n",ans); } }

【经典题|3462: DZY Loves Math II】是否利用了所有条件；
乘法原理与加法原理；