結果
| 問題 | 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;
}