bzoj3462DZY|bzoj3462DZY Loves Math II bzoj3462DZYLovesMathII

文章图片

数据范围：$$2 \leq S \leq 2 * 10^6$$
$$1 \leq n \leq 10^{18}$$
$$ 1 \leq q \leq 10^5$$
【bzoj3462DZY|bzoj3462DZY Loves Math II】数学+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 #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= 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\n",(res+yyc)%yyc); } }

丑陋的卡时代码
转载于:https://www.cnblogs.com/Kong-Ruo/p/8417284.html