kmjp's blog

競技プログラミング参加記です

AtCoder ABC #200 (京セラプログラミングコンテスト2021) : F - Minflip Summation

ARC

DとFでやらかしをしてかなり遅くなった。
https://atcoder.jp/contests/abc200/tasks/abc200_f

問題

0/1/?で構成された文字列Sが与えられる。
SをK回繰り返した文字列をTとし、T中の?をそれぞれ0か1に置き換えた文字列をT'とする。
S中に?がq個あれば、T'は2^(Kq)通り考えられる。

T'に対し、区間を指定して0/1反転する処理を繰り返し、最小回数で全文字をそろえるということを考える。
全T'における、処理回数の総和を求めよ。

解法

まずT'の処理回数の最小値を考える。
T'の先頭文字とそろえることを考えると、T'を先頭から見て行ってT'[0]==T'[i-1]かつT'[i-1] !=T'[i]とのあるiが来ると、1回処理が必要になる。

そこで、まずS1回分に対し、以下を求めよう。これはO(N)で求められる。

  • f(n,a,b) := Sのprefix nにおいて、Sの先頭がaでSのn文字目がbであるような組み合わせ
  • g(n,a,b) := Sのprefix nにおいて、Sの先頭がaでSのn文字目がbである場合の、処理回数の総和

あとはこれらをダブリングしていく。
ダブリングの際、追加で処理が増えたり減ったりするケースに注意。
例えばf(|S|,0,0)のケースとf(|S|,1,1)のケースを連結すると、処理回数が1回増えるし、f(|S|,0,1)のケースとf(|S|,1,0)のケースを連結すると処理回数が1回減る。

string S;
int N,K;
const ll mo=1000000007;

ll from[2][2];
ll to[2][2];
ll fr[2][2];
ll ft[2][2];

ll A[32][2][2];
ll B[32][2][2];

ll RA[2][2];
ll RB[2][2];

void go(ll SA[2][2],ll SB[2][2],ll TA_[2][2],ll TB_[2][2],ll UA_[2][2],ll UB_[2][2]) {
	ll TA[2][2], TB[2][2], UA[2][2], UB[2][2];
	int x,y,a,b,c,d;
	FOR(x,2) FOR(y,2) {
		TA[x][y]=TA_[x][y];
		TB[x][y]=TB_[x][y];
		UA[x][y]=UA_[x][y];
		UB[x][y]=UB_[x][y];
		SA[x][y]=SB[x][y]=0;
	}
	
	FOR(a,2) FOR(b,2) FOR(c,2) FOR(d,2) {
		(SA[a][d]+=TA[a][b]*UA[c][d])%=mo;
		(SB[a][d]+=TB[a][b]*UA[c][d])%=mo;
		(SB[a][d]+=UB[a][b]*TA[c][d])%=mo;
		if(a==b&&b!=c&&c==d) (SB[a][d]+=TA[a][b]*UA[c][d])%=mo;
		if(a==d&&a!=b&&c!=d) (SB[a][d]+=mo-TA[a][b]*UA[c][d]%mo)%=mo;
	}
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>S>>K;
	N=S.size();
	
	if(S[0]=='0'||S[0]=='?') from[0][0]=1;
	if(S[0]=='1'||S[0]=='?') from[1][1]=1;
	for(i=1;i<N;i++) {
		ZERO(to);
		ZERO(ft);
		FOR(x,2) {
			if(S[i]=='0'||S[i]=='?') {
				(to[x][0]+=from[x][0])%=mo;
				(to[x][0]+=from[x][1])%=mo;
				(ft[x][0]+=fr[x][0])%=mo;
				(ft[x][0]+=fr[x][1])%=mo;
				if(x==1) (ft[1][0]+=from[1][1])%=mo;
			}
			if(S[i]=='1'||S[i]=='?') {
				(to[x][1]+=from[x][0])%=mo;
				(to[x][1]+=from[x][1])%=mo;
				(ft[x][1]+=fr[x][0])%=mo;
				(ft[x][1]+=fr[x][1])%=mo;
				if(x==0) (ft[0][1]+=from[0][0])%=mo;
			}
		}
		
		
		swap(from,to);
		swap(fr,ft);
	}
	
	FOR(x,2) FOR(y,2) A[0][x][y]=from[x][y], B[0][x][y]=fr[x][y];
	
	int first=1;
	FOR(i,30) {
		go(A[i+1],B[i+1],A[i],B[i],A[i],B[i]);
		if(K&(1<<i)) {
			if(first) {
				first=0;
				FOR(x,2) FOR(y,2) RA[x][y]=A[i][x][y],RB[x][y]=B[i][x][y];
			}
			else {
				go(RA,RB,RA,RB,A[i],B[i]);
			}
		}
	}
	
	ll ret=0;
	FOR(x,2) FOR(y,2) ret+=RB[x][y];
	cout<<ret%mo<<endl;
	
}

まとめ

連結時の場合分けミスでWAを重ねてしまった。