数据范围：$$2 leq S leq 2 * 10^6$$
$$1 leq n leq 10^{18}$$
$$ 1 leq q leq 10^5$$
数学+dp
题解写一年系列...
观察一下原题，
（1）因为每个$p_i$必须出现，所以我们可以把$n$减去$sum p_i$来转化为每个$p_i$可以不出现
（2）根据$S$的范围，我们发现$k$不超过$20$(实际上不会超过$7$)
（3）$S$中不会含有完全平方因子
（4）事实上，我们拆出来的式子一定是形如$$sum p_i * c_i=n$$
每个$p_i$都是$S$的因数 所以$p_i * c_i$得到的结果一定是$X cdot S + Y cdot c_i$
把$c_i$分成$a_i=c_i/(S/p_i),b_i=c_i mod (S/p_i)$
枚举$m$，$p_1*b_1+p_2*b_2+...+p_k*b_k=n-m*S$
这个可以用背包的方式预处理，剩下的可用插板法得到
#include<bits/stdc++.h> #define LL long long using namespace std; const LL yyc = 1e9+7; const LL maxn = 2e6+10; LL dp[2][maxn << 3]; LL orz[20],cnt; LL s,n,q; inline LL ksm(LL a,LL b) { LL res=1; while(b) { if(b&1)(res*=a)%=yyc; (a*=a)%=yyc; b>>=1; } return res; } inline LL C(LL n,LL m) { n++,m--;n=n+m-1; LL res=1; for(LL i=n;i>=n-m+1;i--) res=(res*(i%yyc))%yyc; for(LL i=1;i<=m;i++) res=res*ksm(i,yyc-2)%yyc; return res; } LL solve() { LL now=0,pre=1; memset(dp[now],0,sizeof(dp[now])); dp[now][0]=1; for(LL i=1;i<=cnt;i++) { now^=1,pre^=1;memset(dp[now],0,sizeof(dp[now])); LL bou=s/orz[i]-1; for(LL j=0;j<orz[i];j++) { LL sum=0; for(LL k=0;k <= (s*cnt-j)/orz[i];k++) { sum+=dp[pre][k*orz[i]+j];sum=sum%yyc; if(k >= bou+1)sum-=dp[pre][(k-bou-1)*orz[i]+j]; dp[now][k*orz[i]+j]=sum; } } } return now; } int main() { scanf("%lld%lld",&s,&q);LL x=s; LL len=sqrt(s); for(LL i=2; i<=len;i++) { if(s%i == 0) s/=i,orz[++cnt]=i; if(s%i == 0) { while(q--)puts("0"); return 0; //huaji } } if(s>1)orz[++cnt]=s;s=x; LL now=solve(); while(q--) { LL res=0; scanf("%lld",&n); for(LL i=1;i<=cnt;i++)n-=orz[i]; if(n < 0) { puts("0"); continue; } LL m=n/s,k=n-m*s; for(LL i=0;i<=min(m,cnt);i++) res=(res+dp[now][i*s+k]*C(cnt+m-i-cnt,cnt%yyc)%yyc)%yyc; printf("%lld ",(res+yyc)%yyc); } }