SDOI2016 排列計數

來自專欄 Code++2 人贊了文章【P4071】[SDOI2016]排列計數 - 洛谷?

www.luogu.org

昨天晚上被Codeforces Math Round暴虐，今天又被洛谷隨機了一道數學題……

不過這道數學題還是很友好的，畢竟結論一眼就出來了

我們觀察題目的要求：

所有1~n的排列A中恰好有m個的排列的個數

那麼我們假設一開始的排列就是，然後考慮從中選出m個數不動，剩下的n-m個數進行排列組合

一開始我天真地以為把剩下的數全排列即可，後來發現不對，會有很多不合法的情況出現，還要把全排列中可能出現的的情況給容斥掉

這裡涉及到「錯排問題」：

錯排問題：把n個數1..n投進n個位置1..n，使得每個數都不在自己對應的位置上，請問有幾種投法

假設表示問題的答案，非常顯然，有，加下來推導的情況，這種情況可以分為兩方面：

把這個數放到位置n，這樣剩下的數有n-2個位置可以放
不把這個數放到n，這樣剩下的數有n-1個位置可以放

又因為把一個數放到某一個位置裏有n-1種方法（不能放在它自己對應的那個位置），因此我們得到遞推式： $D_i=(i-1) imes (D_{i-2}+D_{i-1})$

最後根據分步計數的乘法原理，我們可以得到答案為 $C^m_n imes D_{n-m}$ ，注意特殊情況需要特判，乘法逆元搞一搞就好了

#include <cstdio>#define N 1000100#define p 1000000007long long pow_mod(long long a, long long b){ long long ans = 1; a %= p; for (; b; b >>= 1) { if (b & 1) ans = ans * a % p; a = a * a % p; } return ans;}int T, n, m;long long f[N], d[N];int main(){ //freopen("test.in", "r", stdin); f[0] = 1; d[1] = 0; d[2] = 1; for (int i = 1; i <= N; ++i) { f[i] = f[i - 1] * i % p; if (i >= 3) d[i] = (i - 1) * (d[i - 2] + d[i - 1]) % p; } scanf("%d", &T); while (T--) { scanf("%d%d", &n, &m); if (n - m == 1) printf("0 "); else if (m == 0) printf("%lld ", d[n]); else if (n == m) printf("1 "); else printf("%lld ", 1LL * f[n] * pow_mod(f[n - m], p - 2) % p * pow_mod(f[m], p - 2) % p * d[n - m] % p); } return 0;}