SRM 644 div1 med:MakingTournament

やっとわかった…多分3日くらい考えてた。

問題:N人がK回戦のトーナメントをする。1回の試合は2人以上なら何人参加しても良いが,勝者は1人のみである。K回勝ち抜く人は何人いても良い。このようなトーナメントの作り方は何通りあるか。

解法:状態として,「i回戦を勝ち抜いた人がいるかいないか(i=0〜K)」というものを考える。例えば,1回戦を勝ち抜いた人と3回戦を勝ち抜いた人がいる場合,状態は001010(右から1番目と3番目のビットが立っている)とかなります。
で,次のように考えることによって,行列の累乗の計算(いわゆるオートマトン)に帰着させます。知らない人いたら蟻本のp180あたり読んだほうが良いですね。
・ある人を追加する時,その人がどれだけ勝つかに依存して,上で説明した状態を遷移させる

具体的に言うと,例えば今の状態が001011だとすると,次の人を参入させた時,
・1回戦で負ける
・2回戦で負ける
・2回戦まで勝ち抜く(そのあとは3回戦を勝った人がいないので考えない)
という3通りがあります。それぞれの場合において,状態の遷移は,
・001011->001011(1回戦に参加する人が増えたと考える。あとでこの人たちに勝つ人がやってくる)
・001011->001010(1回戦に参加していた人たちが皆負けて,今回考慮した人が2回戦に勝ち進んだ。あとで2回戦でこの人たちをやっつける人が来る)
・001011->001100(1,2回戦に参加していた人たちが皆負けて,現在2回戦に勝ち残った人,3回戦に勝ち残った人しかいない)
という状態遷移をします。注意が必要なのは,K回戦を勝ち抜いた場合の状態遷移ですが,これは
・111111->000000となります(実際にはオーバーフロー的な感じで111111->1000000となっているイメージ)。
ここまでイメージできれば後は簡単で,N人参入するのだから行列はN乗すればOKです。最終的な状態は参加者が負けるかK回勝ち抜けるかのどっちかになっていないといけないので,題意の状態は000000という感じになっています。
以下ソースコード。なんかめっちゃ遅いんだよなぁ…500msくらいかかった。

typedef vector<vector<ll> > matrix;
const ll MOD = 1e9+7;

matrix mul(const matrix& A, const matrix& B) {
    int n = A.size();
    matrix ret(n, vector<ll>(n));
    for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {
        for (int k = 0; k < n; k++) {
            ret[i][j] += A[i][k] * B[k][j];
            ret[i][j] %= MOD;
        }
    }
    return ret;
}

matrix powMat(matrix A, ll p) {
    int n = A.size();
    matrix ret(n, vector<ll>(n));
    for (int i = 0; i < n; i++) ret[i][i] = 1;
    while (p) {
        if (p&1) {
            ret = mul(ret, A);
        }
        A = mul(A, A);
        p >>= 1;
    }
    return ret;
}

class MakingTournament {
public:
    int howManyWays(long long N, int K) {
        int kk = 1<<(K+1);
        matrix Mat(kk, vector<ll>(kk));
        for (int i = 0; i < (1<<K); i++) {
            for (int j = 0; j <= K; j++) {
                if ((i&((1<<j)-1)) == (1<<j)-1) {
                    int x = (i^((1<<j)-1)) | 1<<(j);
                    if (j == K) x = 0;
                    Mat[x][i] = 1;
                }
            }
        }
        matrix Mat2 = powMat(Mat, N);
        return Mat2[0][0]%MOD;
    }
};