CodeTON Round 3 : F. Majority

これも本番かなり手間取った。
https://codeforces.com/contest/1750/problem/F

問題

N要素の01で構成される数列Sのうち、以下の処理を繰り返して全要素1にできるものは何通りか。

S[i]=S[j]=1かつ、x∈[i,j]においてS[x]=1となるxは半分以上である場合、x∈[i,j]においてS[x]=1にできる。

解法

f(n) := n要素の数列Aのうち、処理を繰り返して全要素1にできるものの組み合わせ数
とする。Aの両端は1であることが必須なので、残り要素の決め方2^(n-2)通りのうち、条件を満たさないものを引くことを考える。
想定解はO(N^2)のようだが、O(N^3)でも定数倍高速化を頑張るとどうにか通る。

int N;
ll mo;
ll p2[5050];
ll ok[5050];

__int128 dp[5050];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>mo;
	
	p2[0]=1;
	FOR(i,5010) p2[i+1]=p2[i]*2%mo;
	
	ok[1]=ok[2]=1;
	for(i=3;i<=N;i++) {
		if(i>2501&&i!=N) continue;
		ZERO(dp);
		for(j=1;2*j<i;j++) {
			dp[2*j+1]=ok[j];
		}
		ll ng=0;
		for(j=1;j<=i;j++) {
			(dp[j]+=dp[j-1])%=mo;
			dp[j]%=mo;
			for(x=1;j+3*x+1<i;x++) {
				(dp[j+3*x+1]+=dp[j]*ok[x]);
			}
			if((i-j)%2==0) 	(ng+=(ll)dp[j]*ok[(i-j)/2])%=mo;
		}
		(ok[i]=p2[i-2]+mo-ng)%=mo;

	}
	
	cout<<ok[N]<<endl;
	
}

まとめ

どうにか通ってよかった。