結果

問題 No.2747 Permutation Adjacent Sum
ユーザー kmjp
提出日時 2024-04-24 00:01:33
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 587 ms / 3,000 ms
コード長 4,766 bytes
コンパイル時間 2,185 ms
コンパイル使用メモリ 199,904 KB
最終ジャッジ日時 2025-02-21 08:46:59
ジャッジサーバーID
（参考情報） 		judge4 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0