Codeforces #1077 : Div1 D. Cool Problem

Cool...か？
https://codeforces.com/contest/2187/problem/D

問題

整数X,Yと、0/1/?で構成されるN文字の文字列Sが与えられる。
(N+1)要素の整数列Cを、以下のように作る。

• C[0]=0
• S[i]='0'またはS[i]='?'のとき、C[i+1]=X+C[i]とできる。
• S[i]='1'またはS[i]='?'のとき、C[i+1]=Y-C[i]とできる。

f(S)を、Cの総和とする。
Sのうち?を適切に埋めたとき、f(S)として作成できる値の総和を答えよ。

解法

f(S)にYの何倍寄与するかがわかると、Xに対しても何倍寄与するかが一意に特定できる。
あとはBitsetを使い、Yの何倍分寄与し得るパターンがあるかを列挙しよう。

int T,N;
ll X,Y;
string S;
const ll mo=998244353;
bitset<102020> A,B;
int V[102020];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>X>>Y>>S;
		A.reset();
		B.reset();
		A[0]=1;
		FORR(c,S) {
			bitset<102020> NA,NB;
			if(c=='0'||c=='?') {
				NA|=A;
				NB|=B<<1;
			}
			if(c=='1'||c=='?') {
				NA|=B;
				NB|=A<<1;
			}
			swap(NA,A);
			swap(NB,B);
		}
		A|=B;
		ll ret=0;
		FOR(i,N+1) {
			if((N-i)%2==0) {
				j=(N-i)/2;
			}
			else {
				j=N-(N-1-i)/2;
			}
			V[j]=i;
		}
		set<ll> SS;
		FOR(i,N+1) if(A[i]) {
			j=V[i];
			ll a=Y*i+X*(1LL*j*(j+1)/2);
			SS.insert(a);
			//cout<<i<<" "<<j<<" "<<a<<endl;
		}
		FORR(a,SS) {
			ret+=a%mo;
		}
		cout<<ret%mo<<endl;
		
	}
}

まとめ

本番ギリギリで解けて良かった。