CF893E Counting Arrays

不难想到对 x x x分解后,得到 x = p 1 c 1 ∗ . . p i c i x=p_1^{c1}*..p_i^{c_i} x=p1c1​∗..pici​​ 每一项 c i c_i ci​的分配都是独立的,问题转化为对每一项 c i c_i ci​分配位置,类似多重集的组合数。 那么负数怎么理解呢,因为最后得到的数字是正数,就是挑0,2,4,6,8…个位置取符号,该系数是二项式系数的偶数项之和 2 n − 1 2^{n-1} 2n−1

/*
Stairs upon the temple
I climb and I crawl in
People travel millions of miles just to see it
But they never conquer this way
*/
#include
using namespace std;
const int maxn = 1e6+5;
const int INF = 1e9+7;
typedef long long ll;
typedef pair pii;
#define all(a) (a).begin(), (a).end()
#define pb(a) push_back(a)
vector G[maxn];
const int mod = INF;
int vis[maxn];ll inv[2*maxn];
ll pw(ll a,ll b){
	ll ans = 1;a%=mod;
	while(b){
		if(b&1) ans = ans*a%mod;
		a =a*a%mod;b>>=1;
	}
	return ans%mod;
}
ll fac[maxn*2];
void init(int n){
	vis[1] = 1;
	for(int i=2;iT;
	while(T--){
		int x,n;cin>>x>>n;
		ll ans = 1;
		while(x!=0&&x!=1){
			ll cnt = get(x);
			if(cnt==0) break;
			ans = ans * C(n+cnt-1,n-1) %mod;	
	    }
	    ans = ans * pw(2,n-1)%mod;
	    cout