Codeforces ECR #091 : F. Strange Addition

微妙に面倒な問題。
https://codeforces.com/contest/1380/problem/F

問題

変則的な足し算を考える。
通常の足し算では、どこかの桁で繰り上がりが発生すると上の桁の値が1増えるが、ここではその代わりに1を挿入し桁数が1増えるとする。

今、大きな整数Sが与えられる。また、そのSを1桁書き換えるようなクエリが与えられる。
クエリ毎に、変則的な足し算において和がSとなる2整数(A,B)の対が何通りあるか求めよ。

解法

Sのうち、1111....111Xのように最下位桁以外1であるような部分は、繰り上がりによって挿入された1がいくつか混ざる可能性がある。
そこで、まずこのパターンをDPにより桁数と最下位桁の数字に合わせて、組み合わせを数え上げよう。
それ以外の桁は、和がYならA,Bの組み合わせは(Y+1)通りである。

あとはSegtreeなりsetなりで1が連続している区間を管理しつつ、桁毎の組み合わせの積を更新していこう。

const ll mo=998244353;

int N,M;
string S;
int X,D;

ll modpow(ll a, ll n = mo-2) {
	ll r=1;a%=mo;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

ll pat[502020][10];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	FOR(i,10) {
		pat[1][i]=i+1;
		pat[2][i]=2*pat[1][i]+9-i;
		for(j=3;j<=501010;j++) pat[j][i]=(2*pat[j-1][i]+8*pat[j-2][i])%mo;
	}
	
	cin>>N>>M>>S;
	FORR(c,S) c-='0';
	
	
	set<int> C;
	C.insert(-1);
	ll ret=1;
	FOR(i,N) {
		C.insert(i);
		int s=i;
		while(i<N-1&&S[i]==1) i++;
		ret=ret*pat[i-s+1][S[i]]%mo;
	}
	C.insert(N);
	
	while(M--) {
		int X,D;
		cin>>X>>D;
		X--;
		if(S[X]!=D) {
			auto it=C.lower_bound(X+1);
			auto p=prev(it);
			if((S[X]!=1&&D!=1) || X==N-1) {
				ret=ret*modpow(pat[*it-*p][S[X]])%mo;
				ret=ret*pat[*it-*p][D]%mo;
				
			}
			else if(S[X]==1) {
				ret=ret*modpow(pat[*it-*p][S[*it-1]])%mo;
				ret=ret*pat[X+1-*p][D]%mo;
				ret=ret*pat[*it-(X+1)][S[*it-1]]%mo;
				C.insert(X+1);
				
			}
			else if(D==1) {
				auto n=next(it);
				x=*p;
				y=*n;
				ret=ret*modpow(pat[*it-x][S[*it-1]])%mo;
				ret=ret*modpow(pat[y-*it][S[y-1]])%mo;
				C.erase(X+1);
				ret=ret*pat[y-x][S[y-1]]%mo;
			}
			S[X]=D;
		}
		cout<<ret<<endl;
	}
	
	
}

まとめ

こういうの本番細かいとこ詰めるのに手間取ってるなぁ。