DZY Loves Math II

内存限制：512 MiB 时间限制：2000 ms 标准输入输出题目类型：传统评测方式：文本比较

输入格式

第一行，两个正整数 S 和 q，q 表示询问数量。
接下来 q 行，每行一个正整数 n。

输出格式

输出共 q 行，分别为每个询问的答案。

对于100%的数据，2<=S<=2*10^6，1<=n<=10^18，1<=q<=10^5;

题解：

我们发现对于每一个S，他一定能分成若干个质数乘积的形式，否则他就不能满足第四条条件，同时S的质因子个数一定小于等于7；

解释：2*3*5*7*11*13*17*19=9699690>2*10^6;

其次，n的范围又太大，导致不能直接跑多重背包；

我们发现S一定是每个质因子的倍数；

因此我们可以把每一个n分成a*S+b的形式，其中a不一定等于n/S，同理b并不一定等于n mod S;

将每个n分成整块与零散块，对于整块的部分，直接用组合数求出；对于零散块，容纳最大的数值为 S的质因子个数*S，这个大小的多重背包开的下；

最后只需将每一种零散块的方案数乘上整块的方案数相加即为所求；

附上代码

查看代码

#include<iostream>#include<cstdio>#include<cstring>#include<cmath>#define ll long longusing namespace std;const int mod=1000000007;ll S,m;ll prime[11];ll dp[14000005];ll inv[10];ll invv[10];//逆 ll tot=0;//因子个数 ll lp=0;//一个因子和 ll n=0;inline ll max(ll a,ll b){return a>b?a:b;}void bag(){ll maxn=S*tot;  dp[0]=1; for(int j=1;j<=tot;j++){ for(ll i=0;i+prime[j]<=maxn;++i){ dp[i+prime[j]]=(dp[i]+dp[i+prime[j]])%mod;}for(ll i=maxn;i>=0;--i){if(i+S<=maxn)dp[i+S]=(dp[i+S]-dp[i]+mod)%mod;//去重 }}}int main(){scanf("%lld%lld",&S,&m);ll now=S;ll p=sqrt(S+0.5);for(ll i=2;i<=p;i++){if(now%i==0){ll cnt=0;prime[++tot]=i;lp+=i;while(now%i==0){now/=i;cnt++;}if(cnt>1){while(m--){scanf("%lld",&n);printf("0\n");}return 0;}}}if(now!=1){prime[++tot]=now;lp+=now;}//for(int i=1;i<=tot;i++){//printf("%d ",prime[i]);//}//printf("\n");bag();inv[0]=invv[1]=inv[1]=1;for(int i=2;i<=7;i++){invv[i]=(mod+(-(mod/i)*invv[mod%i]%mod))%mod;inv[i]=inv[i-1]*invv[i]%mod;}//求逆元 while(m--){scanf("%lld",&n);n-=lp;if(n<0){printf("0\n");continue;}if(n<S){printf("%lld\n",dp[n]);continue;}ll maxp=n/S;ll ans=0;ll o=max(ans,maxp-tot+1);for(ll i=o;i<=maxp;i++){ll tmp=inv[tot-1]%mod;            for(int j=0;j<tot-1;j++)tmp=tmp*((i-1+tot-j)%mod)%mod;//实质就是求组合数             ans=(ans+tmp*dp[n-i*S]%mod)%mod;}printf("%lld\n",ans%mod); }return 0;}

标签：技巧 Loves DZY II Math

免责声明：本网信息来自于互联网，目的在于传递更多信息，并不代表本网赞同其观点。其原创性以及文中陈述文字和内容未经本站证实，对本文以及其中全部或者部分内容、文字的真实性、完整性、及时性本站不作任何保证或承诺，并请自行核实相关内容。本站不承担此类作品侵权行为的直接责任及连带责任。如若本网有任何内容侵犯您的权益，请及时联系我们，本站将会在24小时内处理完毕。