yukicoder #563 : 超高速一人かるた large

解説付き

const int MO = (int)1e9 + 7;
string S[2001];
RollingHash rh[2001];
int f[2001][2001];
mint ans[2001], fact[2001];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N;
    cin >> N;
    rep(i, N) {
        cin >> S[i];
    }

    // 接頭辞の問題=>ソート
    // これで、接頭辞が似ている文字列ほど近くになる。
    sort(S, S + N);
    rep(i, N) {
        rh[i] = RollingHash(S[i]);
    }

    // f[i][j]はiとjを区別するのに読み上げる文字数
    // ただし、f[i][i] = 1
    rep(i, N)rep(j, N) {
        if (i == j)f[i][j] = 1;
        else if (i > j)f[i][j] = f[j][i];
        else {
            // ローリングハッシュで接頭辞が何文字一致しているか調べる
            int ok = 0, ng = min(sz(S[i]), sz(S[j])) + 1, mid;
            while (ng - ok > 1) {
                mid = (ok + ng) / 2;
                (rh[i].getHash(0, mid) == rh[j].getHash(0, mid) ? ok : ng) = mid;
            }
            f[i][j] = ng;
        }
    }
    // 都合
    f[N - 1][N] = 1;

    auto C = combinations(N + 10, MO);

    /*
    すべてのカードの集合について、読み上げられる文字数は読み札の順番によらない。
    なので読み札の順番をインデックス順にする。
    */
    for (int ba = 1; ba <= N; ++ba) {
        mint sm;
        // 前に取ってないのがa
        // つまり、a+1,a+2,...,a+ba-1はすべて取った状態。
        // a+baを次に取る
        for (int a = 0; a + ba < N; ++a) {
            // a+baから見て
            // 手前はaが一番近い。なので接頭辞が近い。
            // 後ろはまだ見てないので必ず残っている。これは直後が一番近い。
            sm += max(f[a][a + ba], f[a + ba][a + ba + 1]);
        }
        // 全体でK個取る
        // 少なくともaは取ってないのでK<=N-1
        for (int K = ba; K <= N - 1; ++K) {
            // a+1,a+2,...,a+ba-1,a+baは確定している。
            // それとaは使ってはいけない。
            // このとき
            // N-ba-1個の中からK-ba個選ぶ
            if (ba != N)ans[K - 1] += sm * C[N - ba - 1][K - ba];
        }
    }

    // 前にとっていないカードが存在しない
    // つまり、いまのところすべてのカードをとっている場合
    // 0,1,...,b-1まではすべて取った状態
    // bを取るときのコストをしらべる
    for (int b = 0; b < N; ++b) {
        // 全部でK枚とる
        for (int K = b+1; K <= N; ++K) {
            // 直後のカードとだけ比較。前のカードは残っていないので
            // 0からbまで全部取った状態から残りを選ぶ。(C[N-b-1][K-b-1])
            ans[K - 1] += mint(f[b][b + 1]) * C[N - b - 1][K - b - 1];
        }
    }

    // 解(パターンとの積)には並び順も必要。階乗
    fact[0] = 1;
    rep(i, N)fact[i + 1] = fact[i] * (i + 1);
    rep(i, N)cout << ans[i] * fact[i + 1] << endl;
}