AtCoder ABC #282 (HHKBプログラミングコンテスト2022 Winter) : G - Similar Permutation

ノーミス全完できたのは良かったね。
https://atcoder.jp/contests/abc282/tasks/abc282_g

問題

整数N,Kが与えられる。
1～Nの順列2つA,Bを考える。
(A[i+1]-A[i])*(B[i+1]-B[i])＞0となるiの数がKとなるような順列対は何通りか。

解法

f(n,a,b,k) := A,Bのprefix n要素を定めたとき、A[n-1]・B[n-1]はn要素中小さい順にa,b番目であり、(A[i+1]-A[i])*(B[i+1]-B[i])＞0となるiの数がkであるような組み合わせの数

とする、A[n]・B[n]が(n+1)要素中小さい順にa'とb'だとすると、aとa'、bとb'の大小関係によりf(n+1,a',b',k)またはf(n+1,a',b',k+1)に遷移する。
このままだと状態がO(N^4)、状態遷移が(N^2)でO(N^6)かかる。
実際はf(n,a,b,k)をaとbに関する2次元の累積和を取ると、状態遷移をO(1)で計算でき、全体でO(N^4)で処理できる。

int N,K;
ll mo;

ll from[101][101][101];
ll to[101][101][101];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K>>mo;
	from[0][0][0]=1;
	for(i=1;i<N;i++) {
		ZERO(to);
		FOR(k,i+1) {
			ll S[105][105]={};
			FOR(x,i+1) FOR(y,i+1) {
				S[x+1][y+1]=(S[x+1][y]+S[x][y+1]+mo-S[x][y]+from[x][y][k])%mo;
			}
			FOR(x,i+1) FOR(y,i+1) {
				(to[x][y][k+1]+=(S[x][y]+S[i+1][i+1]-S[x][i+1]-S[i+1][y]+S[x][y]+4*mo))%=mo;
				(to[x][y][k]+=(S[i+1][y]+S[x][i+1]-2*S[x][y]+4*mo))%=mo;
			}
		}
		
		swap(from,to);
	}
	
	ll ret=0;
	FOR(x,N+1) FOR(y,N+1) ret+=from[x][y][K];
	cout<<ret%mo<<endl;
}

まとめ

O(N^4)想定解の問題でN上限100で出すんだな…。