mayoko’s diary

プロコンとかいろいろ。

TCO15 Round 1A med: AutoGame

TCO15 Round 1Aに参加しました。
結果はmedだけ通ってまぁそこそこといった感じです。レーティングhighest更新出来たので嬉しいです。できれば黄色まで伸びてほしいなぁ…

問題:TopCoder Statistics - Problem Statement

解法:まず前提知識として,グラフの遷移は行列の掛け算で表現することができます。特に各行の和が1のものは,何度行列を掛け算しても行の和が1で一定になります。例えば,以下のようなグラフを考えると,
f:id:mayokoex:20150412083806p:plain
行列はA = \left( \begin{matrix} 0 1 0\\ 1 0 0\\ 0 1 0\end{matrix} \right) というようになります(1行目は頂点1にあったのは2に移動すること,2行目は頂点2にあったものは1に移動すること,...を表す)。
また,今回の問題の場合,ある頂点から遷移できる頂点は1つだけなので各行の和は1です。なので,何度行列を掛け算しても行の和が1で一定です。で,これをどういうふうに使うかというと,例えばもともと頂点1にいたやつは2回移動すると1に戻ってきていますが,これは行列の3乗で表すことができます。なぜなら,A^3 = \left( \begin{matrix} 1 0 0\\ 0 1 0\\ 1 0 0\end{matrix} \right) であるので,これは頂点1にあったのは1に移動すること云々を表しているからです。

これを前提として問題を解きます。問題の条件である「tokenが同じ頂点上にない」というのをこの行列で表すと,「各列に1となるものが1つ以下しかない」ということになります(上の行列の例だと1列目に1が2つありますが,どちらかしか選ぶことができないということです)。しかし,K回すべての移動において上の条件を満たすというのはK回のべき乗すべての行列を調べないといけないのでこのままではダメです。しかし,よく考えるとある回数Mでtokenが一致してしまうと,その後は必ずtokenが一致してしまうことがわかります。よって,K回移動した後の遷移についてのみ考えれば十分ということがわかります。

以下ソースコード

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

// O( n )
matrix identity(int n) {
    matrix A(n, vec(n));
    for (int i = 0; i < n; ++i) A[i][i] = 1;
    return A;
}
// O( n^3 )
matrix mul(const matrix &A, const matrix &B) {
    matrix C(A.size(), vec(B[0].size()));
    for (int i = 0; i < C.size(); ++i)
        for (int j = 0; j < C[i].size(); ++j)
            for (int k = 0; k < A[i].size(); ++k) {
                C[i][j] += A[i][k] * B[k][j];
                C[i][j] %= MOD;
            }
    return C;
}
// O( n^3 log e )
matrix pow(const matrix &A, ll e) {
    if (e == 0) return identity(A.size());
    if (e == 1) return A;
    if (e % 2 == 0) {
        matrix tmp = pow(A, e/2);
        return mul(tmp, tmp);
    } else {
        matrix tmp = pow(A, e-1);
        return mul(A, tmp);
    }
}

class Autogame {
public:
    int wayscnt(vector <int> a, int K) {
        int N = a.size();
        matrix mat(N, vector<number>(N));
        for (int i = 0; i < N; i++) {
            mat[i][a[i]-1] = 1;
        }
        mat = pow(mat, K);
        ll ret = 1;
        for (int i = 0; i < N; i++) {
            int col = 0;
            for (int j = 0; j < N; j++) {
                col += mat[j][i];
            }
            ret *= (col+1);
            ret %= MOD;
        }
        return (int)ret;
    }
};

TCOの1日か2日前にkitayuta氏が「(どっかの)試験では5*5行列を4乗した値がどれになるか選択肢で選ばせる問題があるらしくてやばい」と言ってたんですが,それに対してtozan氏が「グラフ書いて終了」と言ってたのを覚えていたので問題見た瞬間に「グラフじゃね?」と思えました。