yukicoder : No.1620 Substring Sum

典型かな。
https://yukicoder.me/problems/no/1620

問題

1～9からなる文字列Sが与えられる。
この文字列の部分列全通りについて、10進数とみなしたときの値の総和を求めよ。

解法

S[i]がどの程度解に寄与するか考える。

• S[0]～S[i-1]が部分列に含まれるかどうかによって、S[i]の寄与する組み合わせが倍々で増えるので、2^i通り分計上される。
• S[i+1]～S[|S|-1]が部分列に含まれるかどうかによって、S[i]の寄与が10倍になるかならないか変わるので、11^(|S|-i-1)通り分計上される。

そこで、(2^i)*S[i]*11^(|S|-i-1)の総和を求めればよい。

string S;
const ll mo=998244353;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>S;
	ll ret=0;
	ll p=1;
	FORR(c,S) {
		ret=ret+ret*10+p*(c-'0');
		p=p*2%mo;
		ret%=mo;
	}
	cout<<ret<<endl;
}

まとめ

かなりコードが短くなった。