NOMURA プログラミングコンテスト 2020 : F - Sorting Game

Fは無視してEをしっかりやればよかった。
https://atcoder.jp/contests/nomura2020/tasks/nomura2020_f

問題

整数N,Mが与えられる。
0～(2^N-1)の範囲の整数値を取るM要素の整数列Aのうち、以下の条件を満たすものは何通りか。

• 2進数のいくつかの桁において、全要素0にしたとする。
• 隣接する2要素が、1桁だけ異なっているときswap可能とする。上記処理でどの桁の集合を選択されたとしても、昇順にソートできる。

解法

数列の手前と後ろで、後ろの方が小さいのに2桁以上異なる要素対があると不可ということになる。
dp(n,m) := 2進数でn桁未満かつm要素の数列のうち、条件を満たすものの組み合わせ
を考える。dp(0,0)=1から初めてdp(N,M)を求めよう。

まず、dp(n-1,*)が求まっているとする。
次にn桁目がどうなるかを考えよう。

• 0のあと1が続く場合、下(n-1)桁自体が条件を満たしているならそれで問題ない。なので、0と1の切り替わり場所の分選択肢がありえてdp(n,m)+=dp(n-1,m)*(m+1)
• (任意個の0のあと)1が出て、また0が出る(そして末尾に任意個の1がでる)場合を考える。最初の1が出た後最後の0が出るまで下位(n-1)桁は同一でなければならない。
  • もしこの区間長がLとすると、残り(m-L+1)要素については下位(n-1)桁が条件を満たす配置になっていればよい。また、最初の1と最後の0の間は、n桁目は0でも1でもよい

愚直に行うとO(NM^2)になるが、最後のパターンは累積和で求めて行くとO(NM)に落とせる。

int N,M;
const ll mo=1000000007;

ll dp[5050][5050];
ll p2[5050],r2[5050];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M+1) dp[0][i]=1;
	
	p2[0]=r2[0]=1;
	FOR(i,5010) {
		p2[i+1]=p2[i]*2%mo;
		r2[i+1]=r2[i]*(mo+1)/2%mo;
	}
	
	
	for(i=1;i<=N;i++) {
		dp[i][0]=1;
		ll sum=0;
		for(x=1;x<=M;x++) {
			// 000111
			(dp[i][x]+=dp[i-1][x]*(x+1))%=mo;
			if(x>=2) (sum+=(x-1)*dp[i-1][x-1]%mo*p2[M-x])%=mo;
			(dp[i][x]+=sum*r2[M-x])%=mo;
		}
	}
	cout<<dp[N][M]<<endl;
}

まとめ

本番違う方針を取っていた。やっぱりEやるべきだったな。