Submission #23704
Source Code Expand
#include <map>
#include <set>
#include <cmath>
#include <stack>
#include <queue>
#include <string>
#include <vector>
#include <bitset>
#include <fstream>
#include <sstream>
#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
#define li long long int
#define rep(i,to) for(li i=0;i<((li)(to));++i)
#define pb push_back
#define sz(v) ((li)(v).size())
#define bit(n) (1ll<<(li)(n))
#define all(vec) (vec).begin(),(vec).end()
#define each(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)
#define MP make_pair
#define F first
#define S second
/*
#define MAX 100500
map<pair<li,li>, li> dp[MAX][2][2];
map<li, li> next_dp[MAX];
li mod = 1000000007;
li next(li n, li d)
{
if(next_dp[d].find(n) != next_dp[d].end()) return next_dp[d][n];
for(li i = d + 1; i * i <= n; i++)if(n % i == 0) return next_dp[d][n] = i;
return next_dp[d][n] = n;
}
li recur(li n, li d, li rem, li minus, li can_plus)
{
cout << n << " " << d << " " << rem << " " << minus << " " << can_plus << endl;
if(rem < 0) return 0;
if(n < d) return 0;
if(n == 1){
li res = 0;
if(minus) rem--;
if(rem < 0) return 0;
return rem / 2 + 1;
}
map<pair<li,li>, li> &DP = dp[rem][minus][can_plus];
if(DP.find(MP(n, d)) != DP.end()) return DP[MP(n, d)];
li res = 0;
if(n == d){
if(can_plus) res = (res + recur(1, 1, rem - 1, minus, true)) % mod;
res = (res + recur(1, 1, rem - 1, 1 - minus, true)) % mod;
}else{
li next_d = next(n, d);
res = (res + recur(n, next_d, rem, minus, true)) % mod;
if(can_plus) res = (res + recur(n / d, d, rem - 1, minus, true)) % mod;
res = (res + recur(n / d, d, rem - 1, 1 - minus, false)) % mod;
}
return DP[MP(n, d)] = res;
}
int main()
{
li n, m;
cin >> n >> m;
cout << recur(n, 2, m, false, true) << endl;
}
*/
#define CC 35ll
#define MAX 100500
map<li, li> dp[MAX][2];
li C[MAX][CC];
li ONE[MAX][2];
li N, M;
li mod = 1000000007;
vector<li> D;
li one(li rem, li minus)
{
if(rem == 0) return 1 - minus;
li &res = ONE[rem][minus];
if(res != -1) return res;
return res = (one(rem - 1, minus) + one(rem - 1, 1 - minus)) % mod;
}
li recur(li n, li rem, li minus)
{
if(rem < 0) return 0;
if(n == 1){
li used = M - rem;
return C[M][used] * one(rem, minus) % mod;
}
if(dp[rem][minus].find(n) != dp[rem][minus].end()) return dp[rem][minus][n];
li res = 0;
for(li i = 0; i < sz(D) && D[i] <= n; i++){
if(n % D[i] != 0) continue;
res = (res + recur(n / D[i], rem - 1, minus)) % mod;
res = (res + recur(n / D[i], rem - 1, 1 - minus)) % mod;
}
return dp[rem][minus][n] = res;
}
int main()
{
rep(i, MAX) C[i][0] = 1;
rep(i, CC) C[i][i] = 1;
rep(i, MAX)rep(j, min(CC, i))if(j) C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
cin >> N >> M;
li minus = N < 0;
N = abs(N);
for(li i = 2; i * i <= N; i++)if(N % i == 0){
D.pb(i);
if(i * i < N) D.pb(N / i);
}
D.pb(N);
sort(all(D));
memset(ONE, -1, sizeof(ONE));
cout << recur(abs(N), M, minus) << endl;
}
Submission Info
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 |
508 ms |
44796 KB |
00_max2.txt |
AC |
147 ms |
44024 KB |
00_max3.txt |
AC |
140 ms |
43900 KB |
00_min.txt |
AC |
124 ms |
39160 KB |
00_sample_01.txt |
AC |
127 ms |
39160 KB |
00_sample_02.txt |
AC |
126 ms |
39172 KB |
00_sample_03.txt |
AC |
127 ms |
39164 KB |
00_sample_04.txt |
AC |
127 ms |
39292 KB |
01_rnd_00.txt |
AC |
133 ms |
41080 KB |
01_rnd_01.txt |
AC |
129 ms |
39812 KB |
01_rnd_02.txt |
AC |
130 ms |
39288 KB |
01_rnd_03.txt |
AC |
130 ms |
40960 KB |
01_rnd_04.txt |
AC |
129 ms |
40708 KB |
01_rnd_05.txt |
AC |
131 ms |
41216 KB |
01_rnd_06.txt |
AC |
125 ms |
39800 KB |
01_rnd_07.txt |
AC |
128 ms |
39924 KB |
01_rnd_08.txt |
AC |
139 ms |
43772 KB |
01_rnd_09.txt |
AC |
133 ms |
41848 KB |
01_rnd_10.txt |
AC |
132 ms |
41984 KB |
01_rnd_11.txt |
AC |
135 ms |
42364 KB |
01_rnd_12.txt |
AC |
138 ms |
43260 KB |
01_rnd_13.txt |
AC |
132 ms |
41216 KB |
01_rnd_14.txt |
AC |
133 ms |
41720 KB |
01_rnd_15.txt |
AC |
129 ms |
40068 KB |
01_rnd_16.txt |
AC |
132 ms |
42484 KB |
01_rnd_17.txt |
AC |
137 ms |
43892 KB |
01_rnd_18.txt |
AC |
137 ms |
42740 KB |
01_rnd_19.txt |
AC |
129 ms |
39804 KB |
01_rnd_20.txt |
AC |
132 ms |
41600 KB |
01_rnd_21.txt |
AC |
131 ms |
41472 KB |
01_rnd_22.txt |
AC |
126 ms |
40180 KB |
01_rnd_23.txt |
AC |
134 ms |
42108 KB |
01_rnd_24.txt |
AC |
134 ms |
42752 KB |
01_rnd_25.txt |
AC |
137 ms |
43384 KB |
01_rnd_26.txt |
AC |
133 ms |
41840 KB |
01_rnd_27.txt |
AC |
131 ms |
41076 KB |
01_rnd_28.txt |
AC |
130 ms |
41344 KB |
01_rnd_29.txt |
AC |
141 ms |
43456 KB |
04_primes_01.txt |
AC |
141 ms |
43904 KB |
04_primes_02.txt |
AC |
140 ms |
43900 KB |