超高速一人かるた small [yukicoder No.562] - はまやんはまやんはまやん

解説放送

準備中

前提知識

解説

https://yukicoder.me/submissions/199959

今回求めたい値は、かるたを取る全てのパターンの疲労度の期待値ではなく、総和を答えると答えになる。
そのため、今後は総和を頑張って計算することを考える。
　
dp[mask] := maskの集合のかるたを取った時の全パターンの疲労度の総和
としてDPを使って計算していこう。
　
maskの中でまだ取っていないi番目を取ることを考える。
すると、i番目のかるたを取るときの疲労度cは「まだ取られてないi番目以外のかるたとi番目のかるたのLCPのうち最大+1」である。
そして、もうかるたをcn個取ったとすると、この状態となる組み合わせはcn!通りあるため、疲労度cもcn!回足されることになる。
そのため、dp[mask | (1 << i)] += dp[mask] + c * cn!でdp更新ができる。
　
下のコードでは

cn! = com.aPb(cn, cn)
i番目とj番目のLCP = lcp.lcp(i, j)

となっている。ライブラリの全体は上のソースコードにある。

Comb<mint, 101> com;
int N;
string S[20];
mint dp[1 << 20];
//---------------------------------------------------------------------------------------------------
mint ans[20];
void _main() {
    ManyLCP lcp;

    cin >> N;
    rep(i, 0, N) cin >> S[i];
    rep(i, 0, N) lcp.add(S[i]);
    lcp.build();
    
    rep(mask, 0, 1 << N) {
        int cn = 0;
        rep(i, 0, N) if ((mask >> i) & 1) cn++;
        ans[cn] += dp[mask];

        vector<int> ok(N, 0);
        int cnt = 0;
        rep(i, 0, N) if (~(mask >> i) & 1) ok[i] = 1, cnt++;

        rep(i, 0, N) if (ok[i]) {
            int c = 1;
            rep(j, 0, N) if (ok[j] && i != j) c = max(c, lcp.lcp(i, j) + 1);
            dp[mask | (1 << i)] += dp[mask] + com.aPb(cn, cn) * c;
        }
    }
    
    rep(i, 1, N + 1) cout << ans[i] << endl;
}