AtCoder ARC 004 D - 表現の自由 (試験管黄色)

これがインフレ！？ABC 110 D - Factorization に瓜二つ

問題へのリンク

問題概要

整数 を 個の整数の積として表す方法が何通りあるかを、1000000007 で割ったあまりを求めよ。

制約

• 
• 

考えたこと

ほとんど、ABC 110 D - Factorization と一緒。

だが、マイナスもありうるのが違う。

• が正のとき、 個のうち偶数個がマイナス
• が負のとき、 個のうち奇数個がマイナス

となる場合の数を求めて、最後に掛け算すればよい。そしてこの場合の数は、いずれの場合であっても 通りである。

なぜなら、 個の整数からマイナスをつける方法 通りのうち、マイナスの個数が偶数のものと奇数のものがちょうど半々になることが

• 個の要素のうちの 1 つを固定して、その正負を反転することで、マイナスの個数が「偶数」の場合と「奇数」の場合とが 1 対 1 に対応する

ということからわかるからである。

#include <iostream>
#include <vector>
using namespace std;


// 素因数分解
vector<pair<long long, long long> > prime_factorize(long long n) {
    vector<pair<long long, long long> > res;
    for (long long p = 2; p * p <= n; ++p) {
        if (n % p != 0) continue;
        int num = 0;
        while (n % p == 0) { ++num; n /= p; }
        res.push_back(make_pair(p, num));
    }
    if (n != 1) res.push_back(make_pair(n, 1));
    return res;
}


// 二項係数
const int MAX = 210000;
const int MOD = 1000000007;

long long fac[MAX], finv[MAX], inv[MAX];
void COMinit(){
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for(int i = 2; i < MAX; i++){
        fac[i] = fac[i-1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD/i) % MOD;
        finv[i] = finv[i-1] * inv[i] % MOD;
    }
}
long long COM(int n, int k){
    if(n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n-k] % MOD) % MOD;
}

long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}


// main
int main() {
    int N, M;
    COMinit();
    cin >> N >> M;
    auto vec = prime_factorize(abs(N));
    long long res = 1;
    for (auto pa : vec) {
        int k = pa.second;
        long long tmp = COM(M+k-1, k);  // nHk = n+k-1Ck
        res = (res * tmp) % MOD;
    }
    cout << res * modpow(2LL, M-1, MOD) % MOD << endl;
}