【BZOJ 3462】DZY Loves Math II（组合数学+DP）

传送门

显然可以发现$s=prod_{i=1}^{k}p_i$时答案才不为$0$

考虑把每个$p_i$的贡献表示为$k_i*s+b_i*p_i$的形式$(b_ip_i<s)$
那么最终也就是$ssum k_i+sum b_ip_i=n$
由于$b_ip_i<s$,且$k$最多只有$7$
所以$sum k_i$的取值范围很小，为$[frac{n-ks}{s},frac n s]$
考虑枚举每一种取值，那么$sum k_i$方案数就是一个插板法

然后对于$sum b_ip_i$总取值很小，可以暴力背包求
乘起来即可

#include<bits/stdc++.h>
using namespace std;
#define cs const
#define re register
#define pb push_back
#define pii pair<int,int>
#define fi first
#define ll long long
#define se second
#define bg begin
cs int RLEN=(1<<20)+1;
inline char gc(){
	static char ibuf[RLEN],*ib,*ob;
	(ib==ob)&&(ob=(ib=ibuf)+fread(ibuf,1,RLEN,stdin));
	return (ib==ob)?EOF:*ib++;
}
inline int read(){
	char ch=gc();
	int res=0;bool f=1;
	while(!isdigit(ch))f^=ch=='-',ch=gc();
	while(isdigit(ch))res=res*10+(ch^48),ch=gc();
	return f?res:-res;
}
inline ll readl(){
	char ch=gc();
	ll res=0;bool f=1;
	while(!isdigit(ch))f^=ch=='-',ch=gc();
	while(isdigit(ch))res=res*10+(ch^48),ch=gc();
	return f?res:-res;
}
template<class tp>inline void chemx(tp&a,tp b){a<b?a=b:0;}
template<class tp>inline void chemn(tp&a,tp b){a>b?a=b:0;}
cs int mod=1e9+7;
inline int add(int a,int b){return (a+=b)>=mod?(a-mod):a;}
inline int dec(int a,int b){a-=b;return a+(a>>31&mod);}
inline int mul(int a,int b){static ll r;r=1ll*a*b;return (r>=mod)?(r%mod):r;}
inline void Add(int &a,int b){(a+=b)>=mod?(a-=mod):0;}
inline void Dec(int &a,int b){a-=b,a+=a>>31&mod;}
inline void Mul(int &a,int b){static ll r;r=1ll*a*b,a=(r>=mod)?(r%mod):r;}
inline int ksm(int a,int b,int res=1){for(;b;b>>=1,Mul(a,a))(b&1)&&(Mul(res,a),1);return res;}
inline int Inv(int x){return ksm(x,mod-2);}
cs int N=2000005;
int f[2][N*7];
int pr[15];
int q,s,sum,iv,cnt,x;
inline int C(ll t,int num){
	int ret=1;
	for(ll x=t+num-1;x>t;x--)Mul(ret,x%mod);
	Mul(ret,iv);return ret;
}
int main(){
	#ifdef Stargazer
	freopen("lx.in","r",stdin);
	#endif
	x=s=read(),q=read();
	for(int i=2;i*i<=s;i++){
		if(s%i==0){
			s/=i,pr[++cnt]=i;
			if(s%i==0){
				while(q--)puts("0");return 0;
			}
		}
	}
	if(s>1)pr[++cnt]=s;
	s=x;
	for(int i=1;i<=cnt;i++)sum+=pr[i];
	f[0][0]=1;
	int now=0;
	for(int i=1;i<=cnt;i++){
		now^=1;
		memcpy(f[now],f[now^1],sizeof(f[now]));
		for(int j=0;j<i*s;j++){
			if(j>=pr[i])Add(f[now][j],f[now][j-pr[i]]);
			if(j>=s)Dec(f[now][j],f[now^1][j-s]);
		}
	}
	iv=1;
	for(int i=1;i<cnt;i++)Mul(iv,i);iv=Inv(iv);
	while(q--){
		ll n=readl()-sum;int ret=0;
		for(ll t=(n-cnt*s)/s;t<=n/s;t++)Add(ret,mul(C(t,cnt),f[now][n-s*t]));
		cout<<ret<<'
';
	}
}