# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
22342 | past future present (#40) | Fully Generate (KRIII5_FG) | C++14 | 500 ms | 329024 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 <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
const ll mod = 1000000007;
vector<ll> v;
vector<ll> sum;
ll pow(ll a, ll b){
ll t = a;
ll r = 1;
while(b){
if(b&1){
r=r*t%mod;
}
t=t*t%mod;
b>>=1;
}
return r;
}
int main(){
ll n;
scanf("%lld",&n);
v.push_back(0);
sum.push_back(0);
v.push_back(1);
sum.push_back(1);
v.push_back(2);
sum.push_back(3);
if(n<=3){
printf("%d\n",n==1?1:n==2?2:4);
return 0;
}
for(ll i=3;i<40000000;i++){
ll x = lower_bound(sum.begin(), sum.end(), i) - sum.begin();
if(sum.back()+x >= n){
x -= (sum.back()+x-n);
v.push_back(x);
sum.push_back(sum.back()+x);
break;
}
v.push_back(x);
sum.push_back(sum.back()+x);
}
v.push_back(0);
ll x = 1;
ll ans = 1;
for(int i=1;i<v.size()-1;i++){
x=x*i%mod;
if(v[i]!=v[i+1]){
ans=ans*pow(x,v[i])%mod;
x = 1;
}
}
printf("%lld",ans);
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |