Submission #903045
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 >able, 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 >able, 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 subres=1;
for (i64 e: E)
(subres *= modchoose(e+M-1, e, ftable, gtable)) %= MOD;
i64 res=0;
for (i64 i=N<0; i<=M; i+=2)
(res += subres*modchoose(M, i, 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
Set Name |
All |
Score / Max Score |
100 / 100 |
Status |
|
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 |
25 ms |
2340 KB |
00_max2.txt |
AC |
24 ms |
2340 KB |
00_max3.txt |
AC |
24 ms |
2340 KB |
00_min.txt |
AC |
18 ms |
796 KB |
00_sample_01.txt |
AC |
19 ms |
804 KB |
00_sample_02.txt |
AC |
17 ms |
864 KB |
00_sample_03.txt |
AC |
19 ms |
800 KB |
00_sample_04.txt |
AC |
18 ms |
928 KB |
01_rnd_00.txt |
AC |
19 ms |
1316 KB |
01_rnd_01.txt |
AC |
17 ms |
932 KB |
01_rnd_02.txt |
AC |
19 ms |
804 KB |
01_rnd_03.txt |
AC |
20 ms |
1316 KB |
01_rnd_04.txt |
AC |
21 ms |
1316 KB |
01_rnd_05.txt |
AC |
21 ms |
1436 KB |
01_rnd_06.txt |
AC |
19 ms |
924 KB |
01_rnd_07.txt |
AC |
19 ms |
1052 KB |
01_rnd_08.txt |
AC |
23 ms |
2340 KB |
01_rnd_09.txt |
AC |
22 ms |
1572 KB |
01_rnd_10.txt |
AC |
22 ms |
1824 KB |
01_rnd_11.txt |
AC |
23 ms |
1824 KB |
01_rnd_12.txt |
AC |
22 ms |
2084 KB |
01_rnd_13.txt |
AC |
21 ms |
1564 KB |
01_rnd_14.txt |
AC |
22 ms |
1572 KB |
01_rnd_15.txt |
AC |
20 ms |
1052 KB |
01_rnd_16.txt |
AC |
23 ms |
1952 KB |
01_rnd_17.txt |
AC |
25 ms |
2328 KB |
01_rnd_18.txt |
AC |
23 ms |
1952 KB |
01_rnd_19.txt |
AC |
18 ms |
932 KB |
01_rnd_20.txt |
AC |
21 ms |
1568 KB |
01_rnd_21.txt |
AC |
21 ms |
1444 KB |
01_rnd_22.txt |
AC |
18 ms |
1060 KB |
01_rnd_23.txt |
AC |
22 ms |
1700 KB |
01_rnd_24.txt |
AC |
21 ms |
1956 KB |
01_rnd_25.txt |
AC |
24 ms |
2212 KB |
01_rnd_26.txt |
AC |
22 ms |
1696 KB |
01_rnd_27.txt |
AC |
21 ms |
1444 KB |
01_rnd_28.txt |
AC |
21 ms |
1444 KB |
01_rnd_29.txt |
AC |
24 ms |
2212 KB |
04_primes_01.txt |
AC |
26 ms |
2276 KB |
04_primes_02.txt |
AC |
25 ms |
2340 KB |