Submission #22368

#	Time	Username	Problem	Language	Result	Execution time	Memory
22368		past future present (#40)	Fully Generate (KRIII5_FG)	C++14	2 / 7	500 ms	394472 KiB

FG

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
const ll mod = 1000000007;
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);
    sum.push_back(0);
    sum.push_back(1);
    sum.push_back(3);
    if(n<=3){
        printf("%d\n",n==1?1:n==2?2:4);
        return 0;
    }
    ll prev = 2; 
    for(ll i=3;i<40000000;i++){
        ll x = prev;
        if(sum[prev]<=i)prev++;
        if(sum.back()+x >= n){
            x -= (sum.back()+x-n);
            sum.push_back(sum.back()+x);
            break;
        }
        sum.push_back(sum.back()+x);
    }
    sum.push_back(sum.back());
    ll x = 1;
    ll ans = 1;
    for(int i=1;i<sum.size()-1;i++){
        x=x*i%mod;
        if(sum[i]-sum[i-1]!=sum[i+1]-sum[i]){
            ans=ans*pow(x,sum[i]-sum[i-1])%mod;
            x = 1;
        }
    }
    printf("%lld",ans);

}

Compilation message (stderr)

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

• Subtask 1: 2 / 2
• Subtask 2: 0 / 5