Submission #22342

#TimeUsernameProblemLanguageResultExecution timeMemory
22342past future present (#40)Fully Generate (KRIII5_FG)C++14
2 / 7
500 ms329024 KiB
#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)

FG.cpp: In function 'int main()':
FG.cpp:49:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=1;i<v.size()-1;i++){
                  ^
FG.cpp:24:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld",&n);
                     ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...