Submission #5242542


Source Code Expand

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

typedef long long ll;
const ll mod = 1e9 + 7;

ll modpow(ll a, ll b, ll p = 1e9+7){
    if(b == 0)  return 1;

    if(b % 2 == 0){
        ll d = modpow(a, b/2, p);
        return (d*d) % p;
    }else{
        return (a%p * modpow(a, b-1, p)) % p;
    }
}

struct ModComb{
    vector<ll> po, inv;
    ll N;

    ModComb(ll n) : N(n), po(n), inv(n) {
        po[0] = 1;
        for(int i = 1; i < N; i++)  po[i] = (po[i-1] * i) % mod;
        inv[N-1] = modpow(po[N-1], mod-2, mod);
        for(int i = N-2; i >= 0; i--)   inv[i] = (inv[i+1] * (i+1)) % mod;
    }
    
    ll nCk(ll n, ll k){
        if(k == 0)  return 1;
        if(n < k)   return 0;
        return (((po[n]*inv[n-k])%mod)*inv[k])%mod;
    }

    ll nPk(ll n, ll k){
        if(k == 0)  return 1;
        if(n < k)   return 0;
        return (po[n]*inv[n-k])%mod;
    }

    ll nHk(ll n, ll k){
        if(n == 0 && k == 0)    return 1;
        return nCk(n+k-1, k-1);
    }
};

int main(){
    ll n, m;
    cin >> n >> m;
    ModComb mc(2*m+1);
    bool minus = n < 0;
    n = abs(n);
    ll ans = 1;
    for(int i = 2; i*i <= n; i++){
        int cnt = 0;
        while(n%i == 0) n /= i, cnt++;
        if(cnt) ans = ans * mc.nHk(cnt, m) % mod;
    }
    if(n != 1)  ans = ans * mc.nHk(1, m) % mod;
    ll mul = 0;
    int x = minus ? 1 : 0;
    while(x <= m){
        mul += mc.nCk(m, x);
        mul %= mod;
        x += 2;
    }
    cout << ans*mul%mod << endl;
    return 0;
}

Submission Info

Submission Time
Task D - 表現の自由 ( Freedom of expression )
User face4
Language C++14 (GCC 5.4.1)
Score 100
Code Size 1577 Byte
Status AC
Exec Time 6 ms
Memory 3328 KB

Judge Result

Set Name All
Score / Max Score 100 / 100
Status
AC × 40
Set Name Test Cases
All 00_max.txt, 00_max2.txt, 00_max3.txt, 00_min.txt, 00_sample_01.txt, 00_sample_02.txt, 00_sample_03.txt, 00_sample_04.txt, 01_rnd_00.txt, 01_rnd_01.txt, 01_rnd_02.txt, 01_rnd_03.txt, 01_rnd_04.txt, 01_rnd_05.txt, 01_rnd_06.txt, 01_rnd_07.txt, 01_rnd_08.txt, 01_rnd_09.txt, 01_rnd_10.txt, 01_rnd_11.txt, 01_rnd_12.txt, 01_rnd_13.txt, 01_rnd_14.txt, 01_rnd_15.txt, 01_rnd_16.txt, 01_rnd_17.txt, 01_rnd_18.txt, 01_rnd_19.txt, 01_rnd_20.txt, 01_rnd_21.txt, 01_rnd_22.txt, 01_rnd_23.txt, 01_rnd_24.txt, 01_rnd_25.txt, 01_rnd_26.txt, 01_rnd_27.txt, 01_rnd_28.txt, 01_rnd_29.txt, 04_primes_01.txt, 04_primes_02.txt
Case Name Status Exec Time Memory
00_max.txt AC 6 ms 3328 KB
00_max2.txt AC 5 ms 3328 KB
00_max3.txt AC 6 ms 3328 KB
00_min.txt AC 1 ms 256 KB
00_sample_01.txt AC 1 ms 256 KB
00_sample_02.txt AC 1 ms 256 KB
00_sample_03.txt AC 1 ms 256 KB
00_sample_04.txt AC 1 ms 256 KB
01_rnd_00.txt AC 3 ms 1536 KB
01_rnd_01.txt AC 2 ms 640 KB
01_rnd_02.txt AC 1 ms 256 KB
01_rnd_03.txt AC 3 ms 1408 KB
01_rnd_04.txt AC 3 ms 1280 KB
01_rnd_05.txt AC 3 ms 1536 KB
01_rnd_06.txt AC 2 ms 640 KB
01_rnd_07.txt AC 2 ms 768 KB
01_rnd_08.txt AC 6 ms 3328 KB
01_rnd_09.txt AC 4 ms 1920 KB
01_rnd_10.txt AC 4 ms 2048 KB
01_rnd_11.txt AC 4 ms 2304 KB
01_rnd_12.txt AC 5 ms 2944 KB
01_rnd_13.txt AC 3 ms 1664 KB
01_rnd_14.txt AC 4 ms 1920 KB
01_rnd_15.txt AC 2 ms 768 KB
01_rnd_16.txt AC 4 ms 2432 KB
01_rnd_17.txt AC 6 ms 3328 KB
01_rnd_18.txt AC 5 ms 2688 KB
01_rnd_19.txt AC 2 ms 640 KB
01_rnd_20.txt AC 4 ms 1792 KB
01_rnd_21.txt AC 3 ms 1792 KB
01_rnd_22.txt AC 2 ms 896 KB
01_rnd_23.txt AC 4 ms 2176 KB
01_rnd_24.txt AC 5 ms 2688 KB
01_rnd_25.txt AC 5 ms 3072 KB
01_rnd_26.txt AC 4 ms 2048 KB
01_rnd_27.txt AC 3 ms 1536 KB
01_rnd_28.txt AC 3 ms 1664 KB
01_rnd_29.txt AC 5 ms 3072 KB
04_primes_01.txt AC 6 ms 3328 KB
04_primes_02.txt AC 6 ms 3328 KB