[Q] https://atcoder.jp/contests/abc224/tasks/abc224_f

考察さえできればあっという間でした。

12345 があったとして、
1) +1、 +10、+100、+1000、+10000の回数を考察する。
2) +2、+20、+200、+2000の回数を考察する。
3) +3、+30、+300 の回数を考察する。
...

すると、
1) 1, 11, 112, 1124, 11248
2) 0, 2, 22, 224, 2248
3) 0, 0, 4, 44, 448
なる数列を得られる。法則が見えてきそう。

Q. 12345 として
・1 だけ見る( 10000 が与えられた場合と同じ想定 )
 
DP[見てる桁数][10^x] = 何通りの取り方があるか

      1 2 3 4 5 // 桁数
10^0  1 1 2 4 8 // 1
10^1    1 1 2 4 // 10
10^2      1 1 2 // 100
10^3        1 1 // 1000
10^4          1 // 10000

各桁の総和をとる。
base[] = {1, 11, 112, 1124, 11248 ,,,}

これ、どんな増え方？
0*10 + 2^0 = 1
1*10 + 2^0 = 11
11*10 + 2^1 = 112
112*10 + 2^2 = 1124
...
base[i+1] = base[i] * 10 + 2^i で求まりそう。

・2 だけ見る ( 02000 が与えられた場合と同じ想定)
      1 2 3 4 5 // 桁数
10^0    2 2 4 8
10^1      2 2 4
10^2        2 2
10^3          2
10^4 

base2[] = {0, 2, 22, 224, 2248}

これは、さっきの base からindexを1つずらして2倍したものっぽい。
base2[i] = base[i-1] * 2

・3 だけみる ( 00300 が与えられた場合と同じ想定)
      1 2 3 4 5 // 桁数
10^0      4 4 8
10^1        4 4
10^2          4
10^3          
10^4 

base3[] = {0, 0, 4, 44, 448}
これは、base から index - 2 して 4倍 したものっぽい。

base3[i] = base[i-2] * 2^2


1. base[]を求める。
2. 桁がずれたら、base[N-i] * 2^i でbase数を求める。
3. S の値をかけてあげればよさそう

1:11248
2:4496
3:1344
4:352
5:80

A. 17520

実装

string S;
ll N;
mint base[200010];
mint powtwo[200010];

int main(){
 cincout();
 
 cin >> S;
 N = S.size();
 
 base[0] = 1;
 powtwo[0] = 1;
 rep(i, N-1) powtwo[i+1] = powtwo[i] * 2;
 rep(i, N-1){
   base[i+1] = base[i] * 10 + powtwo[max(0LL, i)];
 }
 mint ans = 0;
 rep(i, N){
   mint n = S[i] - '0';
   ans += base[N-1-i] * powtwo[i] * n;
 }
 cout << ans << endl;
}

https://atcoder.jp/contests/abc224/submissions/26818585