SDOI2016-排列計數
發現很多題解都沒有講清楚這道題為什么要用逆元、遞推公式怎么來的， 我，風雨兼程三十載，只為寫出一篇好題解， 還是我來造福大家一下吧，
題目大意：
一個長度為 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)\times(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 \div b) \% MOD\) 時，防止 \(b\) 過大而爆精度，將 \(a \div b\) 轉化為某種簡單的乘法，
若 \(c\) 為 \(b\) 的逆元，則有 \((b \times c) \equiv 1 (mod 模數)\)
那么 \((a \div b) \% MOD\) = \((a \div b) \times 1 \% MOD\) = \((a \div b) \times b \times c \% MOD\) = \((a \times c) \% 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;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/73343.html
標籤：C++
上一篇：結題報告