結果
問題 | No.2747 Permutation Adjacent Sum |
ユーザー | 👑 kmjp |
提出日時 | 2024-04-24 00:01:33 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 430 ms / 3,000 ms |
コード長 | 4,766 bytes |
コンパイル時間 | 2,403 ms |
コンパイル使用メモリ | 200,740 KB |
実行使用メモリ | 81,796 KB |
最終ジャッジ日時 | 2024-04-24 00:01:51 |
合計ジャッジ時間 | 16,132 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 286 ms
62,932 KB |
testcase_01 | AC | 197 ms
51,004 KB |
testcase_02 | AC | 236 ms
57,632 KB |
testcase_03 | AC | 186 ms
50,920 KB |
testcase_04 | AC | 286 ms
63,708 KB |
testcase_05 | AC | 414 ms
81,460 KB |
testcase_06 | AC | 308 ms
64,540 KB |
testcase_07 | AC | 283 ms
62,540 KB |
testcase_08 | AC | 323 ms
72,664 KB |
testcase_09 | AC | 422 ms
78,364 KB |
testcase_10 | AC | 195 ms
53,540 KB |
testcase_11 | AC | 282 ms
62,632 KB |
testcase_12 | AC | 172 ms
50,560 KB |
testcase_13 | AC | 206 ms
55,780 KB |
testcase_14 | AC | 334 ms
71,160 KB |
testcase_15 | AC | 401 ms
78,008 KB |
testcase_16 | AC | 268 ms
63,132 KB |
testcase_17 | AC | 386 ms
76,372 KB |
testcase_18 | AC | 380 ms
75,540 KB |
testcase_19 | AC | 165 ms
51,916 KB |
testcase_20 | AC | 292 ms
63,544 KB |
testcase_21 | AC | 374 ms
72,612 KB |
testcase_22 | AC | 403 ms
73,780 KB |
testcase_23 | AC | 235 ms
61,216 KB |
testcase_24 | AC | 276 ms
61,836 KB |
testcase_25 | AC | 251 ms
57,232 KB |
testcase_26 | AC | 341 ms
71,488 KB |
testcase_27 | AC | 347 ms
73,044 KB |
testcase_28 | AC | 326 ms
72,480 KB |
testcase_29 | AC | 278 ms
63,756 KB |
testcase_30 | AC | 430 ms
81,792 KB |
testcase_31 | AC | 404 ms
81,580 KB |
testcase_32 | AC | 388 ms
81,668 KB |
testcase_33 | AC | 423 ms
81,660 KB |
testcase_34 | AC | 393 ms
81,796 KB |
testcase_35 | AC | 151 ms
50,304 KB |
testcase_36 | AC | 141 ms
50,304 KB |
testcase_37 | AC | 140 ms
50,304 KB |
testcase_38 | AC | 173 ms
50,432 KB |
testcase_39 | AC | 135 ms
50,176 KB |
testcase_40 | AC | 144 ms
50,176 KB |
testcase_41 | AC | 134 ms
50,176 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; typedef signed long long ll; #define _P(...) (void)printf(__VA_ARGS__) #define FOR(x,to) for(x=0;x<(to);x++) #define FORR(x,arr) for(auto& x:arr) #define FORR2(x,y,arr) for(auto& [x,y]:arr) #define ALL(a) (a.begin()),(a.end()) #define ZERO(a) memset(a,0,sizeof(a)) #define MINUS(a) memset(a,0xff,sizeof(a)) template<class T> bool chmax(T &a, const T &b) { if(a<b){a=b;return 1;}return 0;} template<class T> bool chmin(T &a, const T &b) { if(a>b){a=b;return 1;}return 0;} //------------------------------------------------------- int N,K; const ll mo=998244353; /* ll cur=1; _P("{%d,%d},\n",0,1); for(i=1;i<=1010000000;i++) { cur=cur*i%mo; if(i%10000000==0) _P("{%d,%d}\n",(int)i,(int)cur); } */ ll fact(ll v) { static int data[][2]= { {0,1}, {10000000,295201906}, {20000000,160030060}, {30000000,957629942}, {40000000,545208507}, {50000000,213689172}, {60000000,760025067}, {70000000,939830261}, {80000000,506268060}, {90000000,39806322}, {100000000,808258749}, {110000000,440133909}, {120000000,686156489}, {130000000,741797144}, {140000000,390377694}, {150000000,12629586}, {160000000,544711799}, {170000000,104121967}, {180000000,495867250}, {190000000,421290700}, {200000000,117153405}, {210000000,57084755}, {220000000,202713771}, {230000000,675932866}, {240000000,79781699}, {250000000,956276337}, {260000000,652678397}, {270000000,35212756}, {280000000,655645460}, {290000000,468129309}, {300000000,761699708}, {310000000,533047427}, {320000000,287671032}, {330000000,206068022}, {340000000,50865043}, {350000000,144980423}, {360000000,111276893}, {370000000,259415897}, {380000000,444094191}, {390000000,593907889}, {400000000,573994984}, {410000000,892454686}, {420000000,566073550}, {430000000,128761001}, {440000000,888483202}, {450000000,251718753}, {460000000,548033568}, {470000000,428105027}, {480000000,742756734}, {490000000,546182474}, {500000000,62402409}, {510000000,102052166}, {520000000,826426395}, {530000000,159186619}, {540000000,926316039}, {550000000,176055335}, {560000000,51568171}, {570000000,414163604}, {580000000,604947226}, {590000000,681666415}, {600000000,511621808}, {610000000,924112080}, {620000000,265769800}, {630000000,955559118}, {640000000,763148293}, {650000000,472709375}, {660000000,19536133}, {670000000,860830935}, {680000000,290471030}, {690000000,851685235}, {700000000,242726978}, {710000000,169855231}, {720000000,612759169}, {730000000,599797734}, {740000000,961628039}, {750000000,953297493}, {760000000,62806842}, {770000000,37844313}, {780000000,909741023}, {790000000,689361523}, {800000000,887890124}, {810000000,380694152}, {820000000,669317759}, {830000000,367270918}, {840000000,806951470}, {850000000,843736533}, {860000000,377403437}, {870000000,945260111}, {880000000,786127243}, {890000000,80918046}, {900000000,875880304}, {910000000,364983542}, {920000000,623250998}, {930000000,598764068}, {940000000,804930040}, {950000000,24257676}, {960000000,214821357}, {970000000,791011898}, {980000000,954947696}, {990000000,183092975}, {1000000000,0}, {1010000000,0} }; if(v>=mo) return 0; int cur=v/10000000*10000000; ll ret=data[cur/10000000][1]; for(int i=cur+1;i<=v;i++) ret=ret*i%mo; return ret; } ll modpow(ll a, ll n = mo-2) { ll r=1;a%=mo; while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1; return r; } ll lagrange(vector<ll>& P,ll x) { const int NUM_=2000003; static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1]; if (fact[0]==0) { inv[1]=fact[0]=factr[0]=1; for (int i=2;i<=NUM_;++i) inv[i] = inv[mo % i] * (mo - mo / i) % mo; for (int i=1;i<=NUM_;++i) fact[i]=fact[i-1]*i%mo, factr[i]=factr[i-1]*inv[i]%mo; } int i; int N=P.size(); if(0<=x&&x<N) return P[x]; vector<ll> R={1},F={1}; for(i=N-1;i>=1;i--) R.push_back(R.back()*((x-i)%mo)%mo); ll p=1; ll ret=0; FOR(i,N) { ll a=p*R.back()%mo*factr[i]%mo; if((N-1-i)%2==0) a=a*factr[N-1-i]%mo; else a=a*(mo-factr[N-1-i])%mo; (ret+=a*P[i])%=mo; R.pop_back(); (p*=(x-i)%mo)%=mo; } return ret%mo; } void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>K; ll ret=fact(N-1)*2; vector<ll> F={0},G={0}; for(i=1;i<=K+1;i++) F.push_back((F.back()+modpow(i,K))%mo); for(i=1;i<=K+2;i++) G.push_back((G.back()+modpow(i,K+1))%mo); ll a=lagrange(F,N); ll b=lagrange(G,N); ret=ret*(N*a%mo+mo-b)%mo; cout<<ret<<endl; } int main(int argc,char** argv){ string s;int i; if(argc==1) ios::sync_with_stdio(false), cin.tie(0); FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin); cout.tie(0); solve(); return 0; }