Submission #22484

#	Time	Username	Problem	Language	Result	Execution time	Memory
22484		past future present (#40)	Fully Generate (KRIII5_FG)	C++14	7 / 7	399 ms	313616 KiB

FG

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
const ll mod = 1000000007;
ll sum[40000000];
int sl = 0;
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[0]=0;
    sum[1]=1;
    sum[2]=3;
    sl = 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[sl-1]+x >= n){
            x -= (sum[sl-1]+x-n);
            sum[sl]=sum[sl-1]+x;
            sl++;
            break;
        }
        sum[sl] = sum[sl-1]+x;
        sl++;
    }
    sum[sl] = sum[sl-1];
    sl++;
    ll x = 1;
    ll ans = 1;
    for(int i=1;i<sl-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: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: 5 / 5