CF893E Counting Arrays

wflengxuenong · 2022-11-07 15:12:26 · 个人记录

/*

符号问题：放偶数个负号：，可放的符号为0，2，y-2 也就是c(y,0)+c(y,2)+...c(y,y-2)/c(y,y-1),正好2^y的一半，也就是2^(y-1)
 分解因式,先不考虑符号。 x=a1*a2*a3*...at 把t各数放入位置1...y，空着的补1.
 如果ai=aj，还要考虑分解后相同的个数，很麻烦。
 我们把x唯一分解 x=a1^p1*a2^p2*...at^pt;
 这样相当于有t种颜色不同的球，每种个数为pi，放入y个不同的盒子，允许空盒。
 每种放置方法相互独立。最后乘起来。

题目的核心是盒子与小球和乘法原理。
*/
#include<bits/stdc++.h>
#define ri register int
using namespace std;
typedef long long ll;

const int M=1e9+7,N=1e6+109;
ll t,n,m,inv[N],fc[N],pw[N],p;
ll qp(ll a,ll b) {
    ll ans=1ll;
    while(b){
        if(b&1)ans=ans*a%M;
        a=a*a%M;
        b/=2;
    }
    return ans;
}
ll C(int x) {//c(x+m-1,m-1)把x个球放入m个盒子，允许空盒。 
    return fc[x+m-1]*inv[m-1]%M*inv[x]%M;
}
int main() {
    cin>>t;
    fc[0]=inv[0]=pw[0]=1ll;
    for(int i=1; i<N; ++i)fc[i]=1ll*i*fc[i-1]%M,pw[i]=2*pw[i-1]%M;
    inv[N-1]=qp(fc[N-1],M-2);
    for(int i=N-1; i; --i)inv[i-1]=i*inv[i]%M;
    while(t--) {
        cin>>n>>m;
        p=pw[m-1];
        for(int i=2,j; i*i<=n; ++i)if(n%i==0) {
                for(j=0; n%i==0; n/=i)++j;
                p=p*C(j)%M;
            }
        if(n>1)p=p*C(1)%M;
        printf("%lld\n",p);
    }
    return 0;
}