yukicoder : No.2747 Permutation Adjacent Sum

うーむ。
https://yukicoder.me/problems/no/2747

問題

整数N,Kが与えられる。
1～NのPermutation Pに対し、隣接要素の差の絶対値のK乗和を考える。
P全通り(N!通り)に対しその総和を998244353で割った余りを求めよ。

解法

式変形するととなる。
Nが大きいので、(N-1)!を998244353で割った余りは、埋め込みで求めておこう。
i^Kの部分は、最初のK+1項を求めればラグランジュ補間で求めることができる。

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;
	
	
}

まとめ

ラグランジュ補間をライブラリ化してたのでコードが短くなった。