題目鏈接
題意：給你兩個(gè)數(shù)$x,y$,讓你構(gòu)造一些長(zhǎng)為$y$的數(shù)列，讓這個(gè)數(shù)列的累乘為$x$，輸出方案數(shù)。
思路:考慮對(duì)$x$進(jìn)行質(zhì)因數(shù)分解，設(shè)某個(gè)質(zhì)因子PiP_iPi?的的冪為$k$,則這個(gè)質(zhì)因子的貢獻(xiàn)就相當(dāng)于把$k$個(gè)PiP_iPi?放到$y$個(gè)盒子中，且盒子可能為空，方案為$C(k+y?1,y)$，然后每個(gè)質(zhì)因子的方案乘在一起即可。最后，因?yàn)樨?fù)號(hào)也會(huì)出現(xiàn)，但$x$為正，所以就是在$y$個(gè)位置上選偶數(shù)個(gè)位置放負(fù)號(hào)，方案為2y?12^{y-1}2y?1再乘起來(lái)即可。

#include<bits/stdc++.h>#define LL long long #define fi first #define se second #define mp make_pair #define pb push_backusing namespace std;LL gcd(LL a,LL b){return b?gcd(b,a%b):a;} LL lcm(LL a,LL b){return a/gcd(a,b)*b;} LL powmod(LL a,LL b,LL MOD){LL ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;} const int N = 2e6 +11; const LL mod=1e9+7; LL Fac[N+33],Inv[N+33]; int p[N+33],a[N+33],cnt; void init(){Fac[0]=1;for(int i=1;i<=N;i++)Fac[i]=(Fac[i-1]*i)%mod;Inv[N]=powmod(Fac[N],mod-2,mod);for(int i=N-1;i>=1;i--)Inv[i]=(Inv[i+1]*(i+1))%mod;Inv[0]=1; } void P(){for(int i=2;i<N;i++){if(!p[i])a[++cnt]=i;for(int j=1;j<=cnt&&1ll*a[j]*i<N;j++){p[a[j]*i]=1;if(i%a[j]==0)break;}} } LL C(int x,int y){return 1ll*Fac[x]*Inv[y]%mod*Inv[x-y]%mod; } int main(){ios::sync_with_stdio(false);init();int t;P();for(cin>>t;t;t--){int x,y;cin>>x>>y;LL ans=1;for(int i=1;i<=cnt&&1ll*a[i]*a[i]<=x;i++){if(x%a[i]==0){int res=0;while(x%a[i]==0)res++,x/=a[i];ans=ans*C(res+y-1,y-1);ans%=mod;}}if(x>1)ans=ans*C(y,y-1)%mod;cout<<ans*powmod(2,y-1,mod)%mod<<endl;}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/pubgoso/p/10759709.html

總結(jié)

以上是生活随笔為你收集整理的Educational Codeforces Round 33 (Rated for Div. 2) E. Counting Arrays的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。