Codeforces #919 : Div2 E. Counting Binary Strings

完答できなかったけど、まぁまぁいい順位だった回。
https://codeforces.com/contest/1920/problem/E

問題

整数N,Kが与えられる。
バイナリ文字列がgoodであるとは、1がちょうど1回だけ登場することを意味する。
バイナリ文字列Sのうち、goodな部分文字列がちょうどN通りあり、かつgoodな部分文字列は最長K文字以下であるようなものは何通りか。

解法

K文字の上限から、1の両隣に0がいくつか並ぶとき、その個数はK-1以下でなければならない。
00010001000....のように1の間に挟まった文字列について、末尾に10000...という文字列を連結することを考える。

f(n,k) := 今までgoodな部分文字列がn通り作れて、末尾に0がk連続しているような文字列の組み合わせ
上記テーブルに対し、末尾に10000...という文字列を追加していくことを考えて行けばよい。

一見O(N^3)あるように見えて、実際はそんなに状態が増えない。

int T;
int N,K;
const ll mo=998244353;
ll dp[2525][2525];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>K;
		FOR(x,N+2) FOR(y,N+2) dp[x][y]=0;
		FOR(x,K) dp[0][x]=1;
		
		FOR(i,N) {
			FOR(x,K) if(dp[i][x]) {
				for(y=0;x+1+y<=K&&i+(x+1)*(y+1)<=N;y++) (dp[i+(x+1)*(y+1)][y]+=dp[i][x])%=mo;
			}
		}
		ll ret=0;
		FOR(i,N) ret+=dp[N][i];
		cout<<ret%mo<<endl;
	}
}

まとめ

本番これかなりあっさり解いたな。