[latexpage]
頭の整理がてら、ABC171のF問題Strivoreの解説をしようと思います。

問題

「好きな英小文字1文字を好きな位置に挿入する」という操作を文字列SにちょうどK回繰り返してできる文字列は何通りあるでしょう？

制約

• K <= 10^6
• size(S) <= 10^6

考え方

• 文字列Sに対してを1文字ずつ足してDPをするのは難しそう
• 文字列Sに操作をK回行った文字列の長さはsize(S)+k文字である

操作後の文字列の長さをn= size(S)+kとします。

この $26^n$ 通りの文字列から求めたい文字列が何個あるか、と考えると問題を以下のように言い換えることができます

長さnの文字列のうち、文字列Sを部分列として含むものは何通りあるか？

これならDPできそうです。

実際、dp[i][j]を「長さiの文字列ででS1〜Sjまでを部分文字列として含む文字列の数」としたらDP可能です。

DP更新式は「Sj文字目の値を選ぶか、それ以外の値を選ぶか」で決まるため

dp[i + 1][j] += dp[i][j] * 25;
dp[i + 1][j + 1] += dp[i][j];

となります。

  ll n = s.size() + k; // 最終的な文字列の長さ

  vvll dp(n + 1, vll(n + 1));
  dp[0][0] = 1;
  rep(i, n) {
    rep(j, n) {
      dp[i + 1][j] += dp[i][j] * 25;
      dp[i + 1][j + 1] += dp[i][j];
    }
  }

  ll ans = 0;
  FOR(i, n - k, n + 1) {
    ans += dp[n][i];
  }

  cout << ans << endl;

本来ならsize(S)文字目以降を
dp[i+1][k] = dp[i][k] * 26;
とし、dp[n][k]とするのが正しいですが、サンプルコードのように、下記式のように和をとっても同じ値になります。

ただし、これではまだO(n^2)であり、TLEしてしまいます。

DPの表と更新式を見ると、これは二項係数であることが分かります。

↓二項定理

よって、求める値は

となります。

 

• 提出コード