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

問題概要

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

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

解説

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

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

最初に、長さの場合を考えましょう。

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

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

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

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

ソースコード

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;
}

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