Submission #22480

#TimeUsernameProblemLanguageResultExecution timeMemory
22480dhsrhkdgus (#40)Fully Generate (KRIII5_FG)C++14
2 / 7
500 ms2804 KiB
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <iostream> #include <memory.h> #include <math.h> #include <assert.h> #include <queue> #include <map> #include <set> #include <string> #include <algorithm> #include <functional> #include <vector> #include <stack> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> Pi; typedef pair<ll,ll> Pll; #define Fi first #define Se second #define pb(x) push_back(x) #define sz(x) (int)x.size() #define rep(i, n) for(int i=0;i<n;i++) #define repp(i, n) for(int i=1;i<=n;i++) #define all(x) x.begin(), x.end() #define ABS(x) (((x) > 0 ) ? (x) : (-(x))) #define MAX2(x, y) (((x) > (y)) ? (x) : (y)) #define MIN2(x, y) (((x) < (y)) ? (x) : (y)) #define MAX3(x, y, z) ( (x) > (y) ? ( (x) > (z) ? (x) : (z) ) : ( (y) > (z) ? (y) : (z) ) ) #define MIN3(x, y, z) ( (x) < (y) ? ( (x) < (z) ? (x) : (z) ) : ( (y) < (z) ? (y) : (z) ) ) #define MID3(val1,val2,val3) MAX2(MIN2(MAX2(val1,val2),val3),MIN2(val1,val2)) #define geti1(X) scanf("%d",&X) #define geti2(X,Y) scanf("%d%d",&X,&Y) #define geti3(X,Y,Z) scanf("%d%d%d",&X,&Y,&Z) #define geti4(X,Y,Z,W) scanf("%d%d%d%d",&X,&Y,&Z,&W) #define GET_MACRO(_1,_2,_3,_4,NAME,...) NAME #define geti(...) GET_MACRO(__VA_ARGS__, geti4, geti3, geti2, geti1) (__VA_ARGS__) #define INF 987654321 #define IINF 987654321987654321 #include <iomanip> ll N; ll g[100500]; ll MOD = 1e9+7; ll fpow(ll x, ll a){ ll res = 1; ll t = x; while( a > 0 ){ if( a&1 ) res = ( res * t ) % MOD; t = (t * t) % MOD; a >>= 1; } return res; } void solve(ll N){ //cin >> N; ll last = 0; ll ans = 1; repp(i,100000){ ll t = 1; if( N <= i * g[i] ){ ll llast = last; for(int j=last+1;j<=last+g[i];j++){ // cout << N << " " << g[i] << endl; if( N <= i ) break; t *= j; t %= MOD; N -= i; llast = j; } //cout << t << " " << i << " " << llast << " " << N << endl; ans *= fpow(t,i); ans %= MOD; ans *= fpow(llast+1,N); ans %= MOD; N = 0; break; } N -= i * g[i]; for(int j=last+1;j<=last+g[i];j++){ t *= j; t %= MOD; } ans *= fpow(t,i); ans %= MOD; last = last + g[i]; if( N <= 0 ) break; } cout << ans << endl; } int main(void){ //freopen("test2.txt","w",stdout); g[1] = 1; cin >> N; for(int i=1;i<=100000;i++){ g[i+1] = 1 + g[i+1 - g[g[i]]]; //N -= g[i+1]; } /* for(int i=1;i<=1000;i++){ solve(i); } */ solve(N); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...