Educational Codeforces Round 33 (Rated for Div. 2) E. Counting Arrays

题目链接

题意：给你两个数x,yx,yx,y,让你构造一些长为yyy的数列，让这个数列的累乘为xxx，输出方案数。

思路:考虑对xxx进行质因数分解，设某个质因子PiP_iPi的的幂为kkk,则这个质因子的贡献就相当于把kkk个PiP_iPi放到yyy个盒子中，且盒子可能为空，方案为C(k+y−1,y)C(k+y-1,y)C(k+y−1,y)，然后每个质因子的方案乘在一起即可。最后，因为负号也会出现，但xxx为正，所以就是在yyy个位置上选偶数个位置放负号，方案为2y−12^{y-1}2y−1再乘起来即可。

#include<bits/stdc++.h>

#define LL long long

#define fi first

#define se second

#define mp make_pair

#define pb push_back

using 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;

}

巴特西

Educational Codeforces Round 33 (Rated for Div. 2) E. Counting Arrays

最新文章

热门文章