# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
22440 | Lazy Against The Machine (#40) | Fully Generate (KRIII5_FG) | C++98 | 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 <ctime>
#include <cstdlib>
using namespace std;
long long arr[60000];
long long nuj[60000];
long long nuj2[60000];
long long str[60000];
constexpr int mod = 1000000007;
// calculate n^k % m
long long modpow(long long n, long long k)
{
long long ret = 1;
n %= mod;
while (k)
{
if (k & 1)
ret = (ret * n) % mod;
n = (n * n) % mod;
k /= 2;
}
return ret;
}
int main()
{
arr[1] = 1;
arr[2] = 2;
nuj[1] = 1;
nuj[2] = 3;
nuj2[1] = 1;
nuj2[2] = 3;
str[1] = 1;
str[2] = 2;
long long sum = 1;
long long start = 2;
long long end = 2;
long long n;
scanf("%lld", &n);
for (int i = 2;; i++)
{
for (int j = 0; j < arr[i]; j++)
{
arr[start + j] = i;
nuj[start + j] = nuj[start + j - 1] + i;
nuj2[start + j] = nuj2[start + j - 1] + arr[start + j] * (start + j);
str[start + j] = str[start + j - 1] + arr[start + j - 1];
if (nuj2[start + j] >= n)
{
end = start + j;
goto hell;
}
}
start += arr[i];
}
hell:
long long result = 1;
for (long long i = 2; i < end; i++)
{
long long r = 1;
for (long long j = str[i]; j < str[i + 1]; j++)
r = (r * j) % mod;
result = (result * modpow(r, i)) % mod;
}
long long rem = n - nuj2[end - 1];
long long rr = end;
for (long long j = str[end];; j++)
{
if (rem < rr)
{
result = (result * modpow(j, rem)) % mod;
break;
}
rem -= rr;
result = (result * modpow(j, rr)) % mod;
}
printf("%lld\n", result);
return -0;
}