Strivore [AtCoder Beginner Contest 171 F]

https://atcoder.jp/contests/abc171/tasks/abc171_f

前提知識

• 数え上げテク greedyからの帰着

解説

https://atcoder.jp/contests/abc171/submissions/14635205

数え上げで最も気にするべきことは、重複して数えてしまわないかということである。
今回も問題は適当にやると容易に重複してしまいそうな感じがする。
これは例題をやったことが無いと厳しいと思う。
greedyからの帰着をする。
説明としてN=|S|としておこう。

条件から考える

今回作成するべき条件を満たす文字列は、以下条件を満たす必要がある。

• 長さがN+K
• 部分文字列としてSを含む

単純に考えるとこれを満たす文字列は、C(N+K, N) * 26^Kが答えになりそう。
だが、これをしてしまうと重複して数えてしまうので、嬉しくない。
さあ、どうしようか。

greedyを使用して文字列を一意に絞り込む

こういう時は何かを固定することで、ある程度制約を付けることにする。
文字列Aと文字列Bが必ず違う文字列であることを保証できるような制約を考えてみる。
長さで差別化はできないから、部分文字列としてSを含むもので考えてみる。
ある文字列Aの部分文字列としてSを含むかを判定するにはgreedyに先頭から文字を探していけばいい。
すると、部分文字列としてSを含むならN個選ぶと最終的に先頭から何番目かで止まることになる。
このように先頭からgreedyにSを探索したときに、先頭から何個目までで止まるかが違えば、ある2つの文字列は必ず違うものになる。

なので、この特徴量で場合分けしよう。
解法では逆に、greedyで取ったときに最後に何文字あまるかでループを回している。
先頭からgreedyに文字列Sを取ったときに最後にrest文字余る組合せが得られれば良くなった。
restが違って同じ文字列になることはないので、全てについてこれを求めて総和を取ると答え。

rest余るときの組合せ

これはrest余るということは、前からK+N-restに部分文字列としてSが含まれている。
かつ、丁度rest余るということは最後は必ずSの最後になっている必要がある。
S=abcであれば、?a?bcとか??abcとかab??cとかが考えられる。
?に入るのは、greedyに取っていたときに邪魔しないように25通りになる。
しかも、?をどこに入れても25^?の個数通りで変わらない。
?の個数はK+N-rest-N=K-restであるので、?を入れる場所はH(N, K - rest)通り。
それで、?を埋める組合せは25^{K - rest}通りで、余るrest分は何が入っていてもいいので、26^rest通り。
よって、H(N, K - rest25^{K - rest}26^restの総和を取ると答え。

int K; string S;
Comb<mint, 2010101> com;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> K >> S;
    int N = S.length();

    mint ans = 0;
    rep(rest, 0, K + 1) {
        int injection = K - rest;
        ans += com.nHk(N, injection) * (mint(25) ^ injection) * (mint(26) ^ rest);
    }
    cout << ans << endl;
}