Codeforces ECR #137 : G. Antifibonacci Cut

ここまでメモリ制限厳しいの珍しいな。
https://codeforces.com/contest/1743/problem/G

問題

フィボナッチ文字列を以下のように定義する。

• F[0]="0"
• F[1]="1"
• F[n]=F[n-1]+F[n-2] (n≧2)

g(s)を、sをフィボナッチ文字列の連結で表現したときの分割方法の数とする。

文字列の列Sが与えられる。Sのprefix sum vに対するg(v)をそれぞれ答えよ。
なお、この問題のメモリ上限は4MBあり、入力が3MBある。

解法

dp(i,n,m) := i文字目まで処理したとき、今suffixがF(n)のm文字目であるような組み合わせ
とする。n,mのバリエーションは余り多くないのと、dp(i)を計算するときはdp(i-1)がわかればいいので、このテーブルは余り大きなものを持つ必要がない。

int N;
string S;

ll F[60];
const ll mo=998244353;

int dfs(int cur,int pos) {
	if(cur<=1) return cur;
	if(pos<=F[cur-1]) return dfs(cur-1,pos);
	return dfs(cur-2,pos-F[cur-1]);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	F[0]=F[1]=1;
	for(i=2;i<=55;i++) {
		F[i]=F[i-1]+F[i-2];
	}
	
	
	map<int,ll> from[55],to[55];
	int first=1;
	cin>>N;
	FOR(i,N) {
		cin>>S;
		FORR(c,S) {
			if(first) {
				first=0;
				if(c=='0') from[0][1]=1;
				else from[1][1]=1;
				continue;
			}
			c-='0';
			FOR(j,55) to[j].clear();
			FOR(j,55) FORR2(a,b,from[j]) {
				//split
				if(j==50||a<F[j]) {
					(to[c][1]+=b)%=mo;
				}
				//con
				if(j==50) {
					(to[50][1]+=b)%=mo;
				}
				else if(a==F[j]) {
					if(j==0) {
						(to[50][1]+=b)%=mo;
					}
					else if(dfs(j+1,a+1)==c) {
						(to[j+1][a+1]+=b)%=mo;
					}
					else {
						(to[50][1]+=b)%=mo;
					}
				}
				else {
					if(dfs(j,a+1)==c) {
						(to[j][a+1]+=b)%=mo;
					}
					else {
						(to[50][1]+=b)%=mo;
					}
				}
			}
			swap(from,to);
		}
		ll ret=0;
		FOR(j,55) FORR2(a,b,from[j]) if(j==50||a!=F[j]) ret+=b;
		cout<<ret%mo<<endl;
	}
	
	
	
}

まとめ

メモリ制限する系統の問題、あまり面白みを感じたことないな…。