AtCoder ABC #338 : G - evall

もっと楽な方法あるかも。
https://atcoder.jp/contests/abc338/tasks/abc338_g

問題

数字と+と*で構成される文字列が与えられる。
この各部分文字列のうち、先頭と末尾が数字となるものについて、部分文字列を数式とみなして計算したときの値の総和を求めよ。

解法

1. で区切ったそれぞれの項において、部分列を考える。

• 部分列の始まりが項の先頭である
• 部分列の終わりが項の末尾である
  • この2パターンは、直前の+より前を部分列の始まりとしたり、直後の+より後ろを部分列の終わりとできる。
  • よって、項のprefixやsuffixの値を順次評価して行くとよい。
  • X * Yの形の式の後ろに数字dが加わると、以後Y=Y*10+dと考えてよい。
  • X * Yの形の式の前に数字dが加わると、以後X=d*10^|X|+Xと考えてよい。
  • X * Yの形の式の後ろに文字*が加わると、以後X=X*Y、Y=0と考えてよい。
  • X * Yの形の式の前に文字*が加わると、以後X=0、Y=X*Yと考えてよい。

残りは、各項の部分列のうち、始まり・終わりが項の始まり・終わりでないパターンを数え上げよう。

string S;
int N;
int O[1010101];
const ll mo=998244353;
ll p10[1010101];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	
	p10[0]=1;
	FOR(i,1010100) p10[i+1]=p10[i]*10%mo;
	
	cin>>S;
	S+='+';
	N=S.size();
	FOR(i,N) {
		O[i+1]=O[i]+(S[i]!='+'&&S[i]!='*');
	}
	int pre=0;
	ll ret=0;
	FOR(i,N) {
		if(S[i]=='+') {
			int L=O[pre+1];
			int R=O[N]-O[i]+1;
			//左側
			ll A=1,B=0;
			for(x=pre;x<i;x++) {
				if(S[x]=='*') {
					A=A*B%mo;
					B=0;
				}
				else {
					B=(B*10+S[x]-'0')%mo;
					if(x==i-1) {
						(ret+=A*B%mo*L%mo*R)%=mo;
					}
					else {
						(ret+=A*B%mo*L)%=mo;
					}
				}
			}
			//右側
			A=1,B=0,k=0;
			for(x=i-1;x>pre;x--) {
				if(S[x]=='*') {
					A=A*B%mo;
					B=k=0;
				}
				else {
					B=(B+p10[k++]*(S[x]-'0'))%mo;
					(ret+=A*B%mo*R)%=mo;
				}
			}
			{
				ll A=0,B=0,C=0,k=0;
				for(x=pre+1;x<=i-2;x++) {
					if(S[x]=='*') {
						A=(A*B+C)%mo;
						B=C=k=0;
					}
					else {
						y=S[x]-'0';
						B=(B*10+y)%mo;
						k++;
						C=(C*10+y*k)%mo;
						(ret+=A*B+C)%=mo;
					}
				}
			}
			
			pre=i+1;
		}
	}
	cout<<ret<<endl;
}

まとめ

なかなか数字が合わずてこずった。