锐客网

  1. 首页 > it技术 > >

[BZOJ3462]DZY Loves Math II

计数类问题

题目描述
【[BZOJ3462]DZY Loves Math II】[BZOJ3462]DZY Loves Math II
文章图片

2<=S<=2*10^6,1<=n<=10^18,1<=q<=10^5
解题思路
观察可得S的质因子的次幂不超过1，而且不超过6个，设有k个。
这让人浮想联翩。
设质因子 pi选cip i 选 c i 个计入拆分。
那么 n=∑ipicin = ∑ i p i c i 。现在问题是n很大，我们不能直接做，而且有 10510 5 组询问。
n很大，我们考虑一种合法方案，每个 cic i 都不小，而p又是s的约数，我们尝试给 ci%=spic i % = s p i ，我们模了之后一样的方案归为一类，那么对这类的方案我们再把许多的s分配给不同的 pip i ，就可以还原出原来的方案，那么此时假设要分配x个s，那么我们乘上系数 Ck?1x+k?1C x + k ? 1 k ? 1 。
我们现在只需要算出恰好要分配x个s的类的方案就可以算出总方案数了，注意到模了之后每个 cic i 不超过 s/pis / p i ，我们完全可以做一个有个数限制的背包，做出当 ∑i=1..kpici=y∑ i = 1.. k p i c i = y 的每个y的方案数，回答的时候就可以直接弄了，一次询问是O(k)的，不过内存访问似乎不太连续…
注意到一个质因子至少被选一次，那么我们可以先让n减掉每个质因子，这样就不用考虑选没选了。
代码

#include #include #include #include #include //开 O2！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！ using namespace std; #define fo(i,j,k) for(i=j; i<=k; i++) #define fd(i,j,k) for(i=j; i>=k; i--) #define cmax(a,b) (a=(a>b)?a:b) #define cmin(a,b) (a=(a1) d[++td]=S; S=j; f[0]=1; fo(i,1,td) { fo(j,0,S*i) g[j]=f[j]; fo(j,0,S*i) { k=j%d[i]; h[k]=(h[k]+g[j]-((j-S>=0)?g[j-S]:0))%mo; if (h[k]<0) h[k]+=mo; f[j]=h[k]; } } } int ksm(int x,int y) { int ret=1; while (y) { if (y&1) ret=1ll*ret*x%mo; y>>=1; x=1ll*x*x%mo; } return ret; } ll c(ll m,ll n) { ll i,ret=1; fd(i,m,m-n+1) ret=ret*(i%mo)%mo; fo(i,1,n) ret=ret*rev[i]%mo; return ret; } int main() { freopen("1.in","r",stdin); //freopen("1.out","w",stdout); scanf("%d %d",&S,&q); predo(S); fo(i,1,10) rev[i]=ksm(i,mo-2); fo(i,1,q) { ans=0; scanf("%lld",&n); fo(j,1,td) n-=d[j]; if (term||n<0) { printf("0\n"); continue; } fo(j,0,td) { rem=n%S+j*S; di=n/S-j; if (di<0) break; ans=(ans+f[rem]*c(di+td-1,td-1))%mo; } printf("%lld\n",ans); } }

    推荐阅读


    上一篇：那少年，那时光

    下一篇：明星和素人一起生活怎样才能不尬（林更新陈赫是活教材啊）