"SDOI2016 排列計數" 發現很多題解都沒有講清楚這道題為什麼要用逆元、遞推公式怎麼來的。 ~~我，風雨兼程三十載，只為寫出一篇好題解。~~ 還是我來造福大家一下吧。 題目大意： 一個長度為 n 且 1~n 各出現一次的序列，希望在“序列中有且只有 m個數的值 等於 它的位置”條件下求出序列個 ...
發現很多題解都沒有講清楚這道題為什麼要用逆元、遞推公式怎麼來的。 我，風雨兼程三十載，只為寫出一篇好題解。 還是我來造福大家一下吧。
題目大意：
一個長度為 n 且 1~n 各出現一次的序列，希望在“序列中有且只有 m個數的值 等於 它的位置”條件下求出序列個數。答案對1000000007取模。
題目分析：
這道題也許是加強版的“裝錯了的信封”，在“裝錯了的信封”上搞搞比利就好。我們不妨設：
值等於位置的數字 稱 穩定的
值不等於位置數字 稱 不穩定的
穩定的數字由於要保證 值等於位置，故 穩定的數字從序列左到右的值是遞增的
首先我們根據組合數的思想可以知道：
答案 = 穩定的挑選方法數 乘上 不穩定的挑選方法數 。
所以現在我們的目的改成了求出 穩定的挑選方法數 和 不穩定的挑選方法數 。
穩定的挑選方法數：
我們已經知道了 穩定的數字從序列左到右的值是遞增的，那麼我們只需要模擬是哪幾個數是穩定的即可。
不難想到，數量其實就是 在 n 個數中 挑選 m 個數的方案數 。
這不就是組合數裡面的 \(C_n^m\) 嗎？有 \(C_n^m\) = \(\frac{n!}{m!(n-m)!}\)
搞定
不穩定挑選方法數（錯排）：
我們假設已經知道了哪 m 個數是穩定的，那麼我們可以在數組中暫時只看不穩定的數。
也就是 錯排
我們令數組 \(F_x\) 為 有 x 個數字，每個數字均為不穩定的方法數。
由於這些數是不穩定的，那麼就沒有值的大小遞增關係，所以我們對於每一個 \(F_x\) ，都要進行分類討論。
\[假設一個數字 k ,並令 n 位於第 k 位： \begin{cases} 當 k 位於第n位& \text{此時的錯排數為 $F_{n-2}$（因 k 的位置已確定，即求剩下的 n-2 個數的錯排數）}\\ 當 k 不位於第n位& \text{此時的錯排數為 $F_{n-1}$} \end{cases}\]
於是對於每個 \(F_i\) ，有 \(F_i\) = (i - 1) × (\(F_{x-1}\) + \(F_{x-2}\))
所以最終答案為：(\(C_n^m \times\)\(F_{n-m}\))%MOD
具體操作思路：
我們先要初始化，對於 \(C_x^y\) 要初始化階乘，對於 \(F_i\) 要遞推。
然後對於每一組數據，套 (\(C_n^m \times\)\(F_{n-m}\))%MOD 即可。
但是（還沒完）：
由題意得，最終方案數可能很大（所以才要取模），我們在進行 答案累乘時，(\(C_n^m \times\)\(F_{n-m}\))%MOD 可能會爆精度，我們於是要用到：
逆元（inv）
何為逆元（inv）？
比如當有 (a/b)%MOD 時，防止 b 過大而爆精度，將 a/b 轉化為某種簡單的乘法。
若 c 為 b 的逆元，則有 (b * c) ≡ 1 (mod 模數)
那麼 (a/b)%mod = (a/b)1%mod = (a/b)bc%mod = (ac)%mod
即 （一個數 除以 另一個數）%模數 = （一個數 乘上 另一個數的逆元）%模數
如何將逆元應用到該題中
我們初始化逆元數組 inv ，inv 為 階乘的逆元
那對於固定的值於模數，那個值的逆元怎麼求呢？
請你參考費馬小定理
直接給出答案：對於 a % 1000000007 的逆元，為 \(a^{1000000007-2}\)
搞個快速冪就好了
代碼：
#include<bits/stdc++.h>
#include<cctype>
#pragma GCC optimize(2)
#define Max(a,f) a > b ? a : b
#define Min(a,b) a < b ? a : b
#define in(n) n = read()
#define out(a) write(a)
#define outn(a) out(a),putchar('\n')
#define New ll
#define ll long long
#define rg register
using namespace std;
namespace IO_Optimization//優化函數
{
inline New read()//快讀
{
New X = 0,w = 0;
char ch = 0;
while(!isdigit(ch))
{
w |= ch == '-';
ch=getchar();
}
while(isdigit(ch))
{
X = (X << 3) + (X << 1) + (ch ^ 48);
ch = getchar();
}
return w ? -X : X;
}
inline void write(New x)//快輸
{
if(x < 0) putchar('-'),x = -x;
if(x > 9) write(x / 10);
putchar(x % 10 + '0');
}
}
using namespace IO_Optimization;
const int mod = 1000000000 + 7;//模數
const int MAXN = 1000000 + 2;//數組大小常量
ll a[MAXN],f[MAXN],inv[MAXN];
// 階乘 F數組 逆元數組
inline ll ksm(ll a,ll b){//快速冪函數，求逆元
ll ans = 1;
a %= mod;
while(b)
{
if(b & 1)
ans = (a * ans) % mod;
a = (a * a) % mod;
b >>= 1;
}
return ans;
}
int main()
{
a[0] = 1;//初始化
for(rg int i = 1;i <= MAXN; ++i)
{
a[i] = (a[i - 1] * i) % mod;//記得取模
inv[i] = ksm(a[i],mod - 2);//計算逆元
}
f[1] = 0,f[2] = 1,f[3] = 2;//初始化
for(rg int i = 4;i <= MAXN; ++i)
f[i] = ((i - 1) * (f[i - 1] + f[i - 2])) % mod;//遞推公式
int T = read();//多數據輸入
while(T--)
{
int n = read(),m = read(),k = n - m;//輸入n、m，k純屬方便
if(!k)//如果n-m=0，那麼方案數為1
{
puts("1");
continue;
}
if(m == 0)//如果沒有穩定的數，那麼答案直接等於F[n]
{
outn(f[n]);
continue;
}
if(k == 1)//如果n-m=1，則有0個方案
{
puts("0");
continue;
}
outn(((( a[n] * inv[k] ) % mod * inv[m]) % mod * f[k]) % mod);//輸出
//上面是把除法改成乘法逆元了
}
return 0;
}
