Codeforces #729 Div2 : E2. Abnormal Permutation Pairs (hard version)

問題設定は割とシンプル。
https://codeforces.com/contest/1542/problem/E2

問題

整数Nが与えられる。
1～Nの2つの順列(P,Q)の対のうち、

• Pは辞書順でQより小さい
• Pの転倒数はQより大きい

という対は何通りか。

解法

PとQのprefixはn要素目まで同じとき、P[n]より大きなP[0...(n-1)]の要素数と、Q[n]より大きなP[0...(n-1)]の要素数の数は前者の方が小さい。
f(n,k) := n要素の2つのPermutation P,Qの対のうち、先頭要素はP[0]＜Q[0]かつ(Pの転倒数)-(Qの転倒数)=kであるものの数

とする。
f(2,1)=1から初めて、f(n,k)のうちkが負になるものを数えよう。あとはPerm(N,N-n)*f(n,k)の総和を求めるとよい。
f(n,k)からf(n+1,k')の遷移は、P,Qにn+1要素目を追加すると店頭数が-n～n変化することから、f(n,k)に対し重み付きの累積和で計算することができる。

int N;
ll mo;

vector<ll> dp[505],S[505];



void solve() {
	int i,j,k,l,r,x,y; string s;

	cin>>N>>mo;
	
	FOR(i,3) {
		dp[i].resize(260000);
		S[i].resize(260000);
	}
	
	dp[0][130000]=1;
	for(i=1;i<260000;i++) S[0][i]=S[0][i-1]+dp[0][i];
	
	ll ret=0;
	for(i=1;i<=N;i++) {
		
		if(i>=3) {
			swap(dp[i],dp[i-2]);
			swap(S[i],S[i-2]);
			FORR(v,dp[i]) v=0;
		}
		
		int dif=i*(i-1)/2;
		for(j=130000-dif;j<=130000+dif;j++) {
			(dp[i][j-(i-1)]+=dp[i-1][j])%=mo;
			(dp[i][j+1]+=2*(mo-dp[i-1][j]))%=mo;
			(dp[i][j+(i-1)+2]+=dp[i-1][j])%=mo;
		}
		for(j=130000-dif-i;j<260000;j++) (dp[i][j]+=dp[i][j-1])%=mo;
		for(j=130000-dif-i;j<260000;j++) {
			(dp[i][j]+=dp[i][j-1])%=mo;
			(S[i][j]=S[i][j-1]+dp[i][j])%=mo;
		}
		
		
		ll front=1;
		FOR(j,N-i) front=front*(N-j)%mo;
		
		for(int d=1;d<=i-1;d++) {
			int pat=i-d;
			ret+=front*pat%mo*(mo+S[i-1][259999]-S[i-1][130000+d])%mo;
		}
	}
	cout<<ret%mo<<endl;
}

まとめ

この回途中で用事があって撤退したんだっけか。