読者です 読者をやめる 読者になる 読者になる

hogecoder

つたじろう(Tsuta_J) 競技プログラミングの記録

AtCoder Regular Contest 009 C: 高橋君、24歳

問題概要

原文 → C: 高橋君、24歳 - AtCoder Regular Contest 009 | AtCoder

長さ Nの順列 aを並び替えたとき、 a_i \neq i (1-indexed)となる要素が k個になる組み合わせは何通りか。1,777,777,777 (素数) で割った余りを出力せよ。

解説

まず、 a_i = iとなる要素をどこにするかを決めます。これは n個の中から (n-k)個を選ぶ組み合わせであるため、 {}_{n} C_{n-k} = {}_{n} C_{k}と同値です。1,777,777,777を法として計算するため、この計算をするためには逆元の知識が必要ですが、それは他のサイトに委ねます。階乗の計算すると思うけど再帰で書いたらダメですよ、もれなくスタックオーバーフローします。

問題なのは、 a_i \neq iとなるような長さkの順列が何通り作れるかを求めることです。漸化式を求めれば解けそうな雰囲気はしますが、どんな漸化式になるでしょうか。

最初に、長さ n = 1, 2の場合を考えましょう。

長さ1で元と異なる位置に置く組み合わせは当然存在しないので、0通りです。

長さ2では、[1, 2]に対して[2, 1]と変えることで条件を満たせます。これ以外には存在しないため、1通りです。

それでは、長さ n \ \ (n \geqq 3)ではどうなるでしょうか。これは n番目の要素で iを選択したとき、 i番目の要素で nを選択するかどうかで場合分けをすれば求まります。文章で言ってもわかりづらいので、図で(パソコンで書くのめんどくさいので手書き)示します。なお、長さ nの順列でこれを満たす組み合わせの総数を c_nと置いています。

f:id:tsutaj:20161102011904j:plain

ちなみにこのような順列は「完全順列」と呼ばれ、完全順列の総数をモンモール数と呼びます。フランスの数学者、ピエール・モンモールにちなんで名づけられた、らしい。

ソースコード

int const MOD = 1777777777;

ll fact_mod(ll n, ll mod) {
    ll f = 1; repq(i,2,n) f = f * (i % MOD) % MOD;
    return f;
}

// 繰り返し二乗法 (再帰バージョン)
ll mod_pow(ll x, ll n, ll mod) {
    if(n == 0) return 1;
    ll res = mod_pow((x * x) % mod, n / 2 , mod);
    if(n & 1) res = (res * x) % mod;
    return res;
}

// 組み合わせ nCr を求める (modあり)
ll combination_mod(ll n, ll r, ll mod) {
    if(r > n-r) r = n-r;
    if(r == 0) return 1;
    ll a = 1;
    rep(i, 0, r) a = a * ((n-i) % mod) % mod;
    ll b = mod_pow(fact_mod(r, mod), mod-2, mod);
    return (a % mod) * (b % mod) % mod;
}

signed main() {
    int n, k; cin >> n >> k;
    int ans = combination_mod(n, k, MOD);
    int dp[555555]; dp[1] = 0, dp[2] = 1;
    repq(i,3,k) dp[i] = (i-1) * (dp[i-1] + dp[i-2] % MOD) % MOD;
    ans = (ans * dp[k]) % MOD;
    cout << ans << endl;
    return 0;
}

数学に強くなりたいね・・・