# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
22538 | AJAE (#40) | Fully Generate (KRIII5_FG) | C++11 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <cstdio>
#include <vector>
using namespace std;
using ll = long long;
ll MMOD = 1000000007;
ll SEXER;
ll popo(ll a, ll p) {
ll r = 1;
while (p) {
if (p & 1) {
r *= a;
if(r >= MMOD) r %= MMOD;
}
a *= a;
if(a >= MMOD) a %= MMOD;
p >>= 1LL;
}
return r;
}
ll arr[31347599];
int sss[6] = { 0,1,2,4,12,36 };
int main()
{
SEXER = sqrt(MMOD);
ll n;
ll cnt = 0;
ll ans = 1;
scanf("%lld", &n);
if (n <= 5) {
printf("%d\n", sss[n]);
return 0;
}
ll gsize = 4;
arr[0] = 0;
arr[1] = 1;
arr[2] = 2;
arr[3] = 2;
cnt = 1 + 2 + 2;
ans = 2 * 2 * 3 * 3;
bool sw = true;
for (int i = 3; sw; ++i) {
ll &tmp = arr[i];
ll ttmp = 1;
int st = gsize;
for (ll j = 0; j<tmp; ++j) {
arr[gsize] = i;
gsize++;
cnt += i;
if (cnt >= n) {
ans *= popo(ttmp, i);
if(ans >= MMOD) ans %= MMOD;
arr[gsize - 1] = i - (cnt - n);
ans *= popo(gsize - 1, arr[gsize - 1]);
if (ans >= MMOD) ans %= MMOD;
printf("%lld\n", ans);
return 0;
}
ttmp *= (gsize - 1);
if(ttmp >= MMOD) ttmp %= MMOD;
}
ans *= popo(ttmp, i);
if(ans >= MMOD) ans %= MMOD;
}
return 0;
}