SRM 472 div1 med: TwoSidedCards

問題

解法

まず入力の性質に注目します。カードの枚数を n として, 1, 2, ..., n の n 頂点からなるグラフを考えます。

taro[i] から hanako[i] に辺を引く, ということを考えると, 各頂点は必ず次数が 2 になるので, できるグラフは必ず何個かの閉路になります。例えば sample 1 では {1} という閉路と {2 -> 3} という閉路になってたり, sample 3 では {1 -> 3 -> 5} という閉路と {2 -> 4 -> 6 -> 7 -> 8} という閉路が合わさったものになってたりしてます。

すべての数字はたかだか 2 回しか現れませんが, 閉路になっている頂点同士にはこれに関して何らかの関係があるような気がします。例えば, {2 -> 4 -> 1 -> 3} という閉路があったとして, 2 という数字が 2 回現れてかつ 4 という数字が 2 回現れることはありえないです。これを一般化すると, 「ある数字が 2 回現れたとすると, (何回か閉路中の数字が 1 回現れた後) 0 回現れる数字が必ず存在して, そのあとまた 2 回現れる数字が出てくる」ということになります。
わかりにくいので例を挙げると, さっきの {2 -> 4 -> 1 -> 3} で, 2 が 2 回現れたとします。 4 は 1 回現れても良いですが, 2 回出てきてはダメです(2 回現れる数字が出てきた後 0 回現れる数字が出てきてないので)。4 が 1 回現れたとすると, 1 の現れる回数としてありえるのは 1 回か 0 回です。 4 が 0 回現れたとすると, 1 の現れる回数としては 0, 1, 2 どれでも良いです。

このような数字の現れ方は何通りあるのか考えます。サイズが N の閉路で K 個だけ 2 回現れる数字があったとすると, 0 回現れる数字も同様に K 個あります。N 個の中から 2K 個の数字を選ぶと, それらの数字の現れる回数は 2 -> 0 -> 2 -> 0 -> ... となるか, 0 -> 2 -> 0 -> 2 -> ... となるかのいずれかに決まるので, 数字の現れ方は N 個から 2K 個選ぶ方法 * 2( $2{}_N C_{2K}$ ) だけあることになります。ただ, K = 0 の場合は例外で, 0 -> 2 -> 0 -> ... にするも 2 -> 0 -> 2 -> ... にするもないので, 2 で掛ける必要がないです。
数字の現れ方が決まったら, それらの数字の並べ方は, 明らかに N!/(2^K) です。

各 K の値に対する並べ方の和を取れば, サイズ N の閉路に対するカードの並べ方がわかります。
n 枚のカードで出来る各閉路に対するカードの並べ方が分かれば, 答えを得ることが出来ます。

const ll MOD = 1e9+7;

// extgcd
ll extgcd(ll a, ll b, ll& x, ll& y) {
    ll d = a;
    if (b != 0) {
        d = extgcd(b, a % b, y, x);
        y -= (a / b) * x;
    } else {
        x = 1; y = 0;
    }
    return d;
}

// mod_inverse
ll mod_inverse(ll a, ll m) {
    ll x, y;
    extgcd(a, m, x, y);
    return (m+x%m) % m;
}

bool done[55];
ll fact[110], rfact[110];

class TwoSidedCards {
public:
    int theCount(vector <int> taro, vector <int> hanako) {
        int n = taro.size();
        fact[0] = rfact[0] = 1;
        for (int i = 1; i < 110; i++) {
            fact[i] = fact[i-1]*i;
            fact[i] %= MOD;
            rfact[i] = mod_inverse(fact[i], MOD);
        }
        ll ans = 1;
        memset(done, false, sizeof(done));
        int N = n;
        for (int i = 0; i < n; i++) {
            if (done[taro[i]]) continue;
            int cnt = 0, cur = taro[i];
            while (1) {
                if (done[cur]) break;
                done[cur] = true;
                cnt++;
                for (int j = 0; j < n; j++) {
                    if (cur == taro[j]) {
                        cur = hanako[j];
                        break;
                    }
                }
            }
            (ans *= fact[N]) %= MOD;
            (ans *= rfact[cnt]) %= MOD;
            (ans *= rfact[N-cnt]) %= MOD;
            N -= cnt;
            ll tmp = 0;
            for (int k = 0; k <= cnt/2; k++) {
                ll unko = fact[cnt];
                (unko *= rfact[2*k]) %= MOD;
                (unko *= rfact[cnt-2*k]) %= MOD;
                (unko *= fact[cnt]) %= MOD;
                for (int j = 0; j < k; j++) (unko *= rfact[2]) %= MOD;
                if (k>0) (unko *= 2) %= MOD;
                tmp += unko;
            }
            (ans *= tmp) %= MOD;
        }
        return (int)ans;
    }
};

mayoko’s diary

プロコンとかいろいろ。

SRM 472 div1 med: TwoSidedCards

問題

解法