Submission #903046

---

Source Code Expand

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

using i64=long long;
using vx=vector<i64>;

const i64 MOD=1e9+7;

i64 modpow(i64 b, i64 e, i64 p=MOD) {
    /* Exponentiation by squaring */
    // returns n == b**e (mod p)
    i64 n=1, a=b%p;
    while (e) {
        if (e & 1)
            (n *= a) %= p;

        (a *= a) %= p;
        e >>= 1;
    }
    return n;
}

i64 modinv(i64 a, i64 p=MOD) {
    // returns n == a**-1 (mod p)
    return modpow(a, p-2, p);
}

i64 moddiv(i64 a, i64 b, i64 p=MOD) {
    // returns n == a b**-1 (mod p)
    return a*modpow(b, p-2, p) % p;
}

i64 modsub(i64 a, i64 b, i64 p=MOD) {
    // returns n == a-b (mod p)
    return ((a-b)%p+p) % p;
}

void table_modfact(i64 n, vx &ftable, i64 p=MOD) {
    // ftable[i] = i! (mod p)
    ftable.assign(n, 0); ftable[0]=1;

    i64 ub=min(n, p);
    for (i64 i=1; i<ub; ++i)
        (ftable[i] *= i) %= p;
}

void table_modfact(i64 n, vx &ftable, vx &gtable, i64 p=MOD) {
    // ftable[i] = i! (mod p)
    // gtable[i] = i!**-1 (mod p)
    // if ftable[j] == 0, gtable[j] = -1
    ftable.assign(n, 0); ftable[0]=1;

    i64 ub=min(n, p);
    for (i64 i=1; i<ub; ++i)
        (ftable[i] = ftable[i-1]*i) %= p;

    gtable.assign(n, -1); gtable[ub-1]=modinv(ftable[ub-1]);
    for (i64 i=ub; --i;)
        gtable[i-1] = gtable[i]*i % p;
}

i64 modchoose(i64 n, i64 r, const vx &ftable, const vx &gtable, i64 p=MOD) {
    // only for n < p
    i64 res=(ftable[n]*gtable[r])%p;
    (res *= gtable[n-r]) %= p;
    return res;
}

size_t factor_exp(i64 n, vx &fexp) {
    // fexp[i] = exponent of the i-th factor of n
    if (n == 1) {
        fexp.push_back(0);
        return 1;
    }

    for (int i=2; i*i<=n; ++i) {
        i64 cur=0;
        while (n%i == 0) {
            ++cur;
            n /= i;
        }
        if (cur)
            fexp.push_back(cur);
    }

    if (n > 1)
        fexp.push_back(1);

    return fexp.size();
}

int main() {
    i64 N, M;
    scanf("%lld %lld", &N, &M);

    vx E;
    factor_exp(abs(N), E);

    i64 ub=*max_element(E.begin(), E.end())+M+1;
    vx ftable, gtable; table_modfact(ub, ftable, gtable);

    i64 res=0;
    for (i64 i=N<0; i<=M; i+=2)
        (res += modchoose(M, i, ftable, gtable)) %= MOD;

    for (i64 e: E)
        (res *= modchoose(e+M-1, e, ftable, gtable)) %= MOD;

    printf("%lld\n", res);
    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:97:31: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld %lld", &N, &M);
                               ^

Judge Result