Strivore - abc 171 f
#二項係数
まず, 愚直な dp を考える.
rep(i, sz) rep(j, sz(s) + 1) rep(l, 26) { if (s[j] - 'a' == l) add(dp[i + 1][j + 1], dp[i][j]); else add(dp[i + 1][j], dp[i][j]); } cout << dp[sz][sz(s)] << endl;
rep(l, 26) をなくすと以下のようになる.
rep(i, sz) rep(j, sz + 1) { add(dp[i + 1][j + 1], dp[i][j]); add(dp[i + 1][j], 25LL * dp[i][j] % mod); } ll ans = 0; rep3(i, sz(s), sz + 1) add(ans, dp[sz][i]); cout << ans << endl;
sample 1 で dp の違いを確かめる.
1 0 0 0 0 25 1 0 0 0 625 50 1 0 0 15625 1875 75 1 0 390625 62500 3750 101 0 9765625 1953125 156250 6376 0 244140625 58593750 5859375 322026 0 103515583 708984368 205078125 14232051 0 587889561 828124664 835937458 575111451 0
1 0 0 0 0 0 0 0 0 0 25 1 0 0 0 0 0 0 0 0 625 50 1 0 0 0 0 0 0 0 15625 1875 75 1 0 0 0 0 0 0 390625 62500 3750 100 1 0 0 0 0 0 9765625 1953125 156250 6250 125 1 0 0 0 0 244140625 58593750 5859375 312500 9375 150 1 0 0 0 103515583 708984368 205078125 13671875 546875 13125 175 1 0 0 587889561 828124664 835937458 546875000 27343750 875000 17500 200 1 0
5 行目で, 100 1 か 101 か違いが出始める.
下のコードでは, すべて *1 の遷移と *25 の遷移があるのに対し, 上のコードでは, j = sz(s) のとき, *26 の遷移をする.
よって, 下のコードでは, dp[sz] の sz(s) ~ sz までを足す.
手書きで遷移を書いてみると, 二項係数が見えてくる.
よって, dp[sz] の「sz(s) ~ sz までを足す」分の計算量でいい.
ソースコード
https://atcoder.jp/contests/abc171/submissions/14641134
