【ACM組合數學 | 錯排公式】寫信

題目連結：https://ac.nowcoder.com/acm/contest/54484/B

題意很簡單，但是資料範圍偏大。

錯排公式

首先來推導一下錯排公式：

\[D(n) = n!\sum_{k=0}^{n}\frac{(-1)^k}{k!} \]

設一個函數：

\[S_i表示一個排列中p_i = i的方案數 \]

那麼我們可以知道：

\[D(n) = n! - |\cup_{i=1}^{n}S_i| \]

這個表示所有方案數減去至少有一個位置放對的方案數。

現在來考慮一下如何處理後面這個並集，並集往往是不好求的，而交集會好求很多，所以在求並集的時候我們往往採取容斥原理將一個並集轉換成諸多交集的加減運算。

我們用一個圖可以來表示當n = 3的情況：

其中有：

\[|S_1 \cup S_2 \cup S_3| = |S_1| + |S_2| + |S_3| - |S_1 \cap S_2| - |S_1 \cap S_3| - |S_2 \cap S_3| + |S_1 \cap S2 \cap S_3| \]

擴充套件一下就可以得到下面的柿子：

\[|\cup_{i=1}^{n}S_i| = \sum_{k=1}^{n}(-1)^k\sum_{1\leq i_1 \leq i_2 \leq ... \leq i_k \leq n}|S_{i1}\cap S_{i2} ... \cap S_{ik}| \]

然後有：

\[\sum_{1\leq i_1 \leq i_2 \leq ... \leq i_k \leq n}|S_{i1}\cap S_{i2} ... \cap S_{ik}| = C_{n}^{k}(n-k)! \]

這個表示啥呢，左邊這個柿子的含義其實是i1 ~ ik都放對了，其他位置上無所謂的方案數，就等同於在n個位置中選擇k個放對，剩下的隨便放的方案數。

所以可得下面的柿子：

\[|\cup_{i=1}^{n}S_i| = \sum_{k=1}^{n}(-1)^kC_{n}^{k}(n-k)! \]

然後化簡得：

\[|\cup_{i=1}^{n}S_i| = \sum_{k=1}^{n}\frac{(-1)^k n!}{k!} \]

然後代回到一開始的答案表示式中：

\[D(n) = n! - \sum_{k=1}^{n}\frac{(-1)^k n!}{k!} \]

把n!提出來，再化簡一下得到：

\[D(n) = n! \sum_{k=0}^{n}\frac{(-1)^k}{k!} \]

回到本題

但是有這個柿子依然不好寫這題，這題如果是1e7就可以直接O(n)寫了，但是這題是1e9的資料範圍，可以考慮一下分段打表（一般要求函數可以遞推），但是這個表示式好像不是很好打，我們來分析一下。

首先網上有一個比較有名遞推式（證明略）：

\[D(n) = (n-1)[D(n - 1) + D(n - 2)] \]

這個遞推需要用到前兩項，也就是說我們需要打兩個表，然後才可以做，有點麻煩，但是其實是可以只用一項的。

我看網路上都沒有用下面這種方式遞推的，我在這裡寫一下。

我們考慮D(n) -> D(n + 1)這樣的轉移：

\[D(n) = n! \sum_{k=0}^{n}\frac{(-1)^k}{k!} \]

\[D(n + 1) = (n + 1)! \sum_{k=0}^{n + 1}\frac{(-1)^k}{k!} \newline = (n + 1)![\sum_{k=0}^{n}\frac{(-1)^k}{k!} + \frac{(-1)^{n + 1}}{(n + 1)!}] \newline = (n + 1)!\sum_{k=0}^{n}\frac{(-1)^k}{k!} + (-1)^{n + 1} \newline = (n + 1) \times n!\sum_{k=0}^{n}\frac{(-1)^k}{k!} + (-1)^{n + 1} \newline = (n+1) \times D(n) + (-1)^{n+1}\]

然後令段大小T = 1e7打表打出D(0), D(T), D(2T) ... D(100T)就好了。

最終的複雜度是O(n)但是常數極小，所以可以過。

Code:

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int p = 1e9 + 7, T = 1e7;

int a[110] =
{
1,824182295,933713113,474482547,930651136,251064654,637937211,229643390,307311871,448853213,
322273426,398890147,194914852,884947442,154199209,881788023,389699639,733217502,601739182,
372305477,213823357,713959988,498202615,196342945,324300550,154001751,974475946,540773759,
467881322,257531902,598680559,367927849,971346692,94577421,617165552,128327758,503709458,
253566817,820144401,13965056,82358069,805941568,533047638,69430220,686678173,297170813,
34546238,323435423,499126069,487532712,468899710,790590914,581347156,955359050,700529992,
518280890,98592091,64544225,988209678,422603955,40661679,174468756,573631136,757555557,
710709955,775098981,499158883,969149294,880429710,42564126,333697951,522067888,579797877,
528967798,717694718,309384913,31308092,316850320,220854491,878646494,963974981,377654637,
705101053,542246848,466289530,750036412,819636314,688721174,464087273,517164631,256789690,
482685016,276682441,473333947,340221393,762927538,624766601,984537252,977632075,34192646,
402182971,977005016
};

int mo(int x){return (x % p + p) % p;}

void solve()
{
	int n;cin >> n;
	int ans = a[n / T];
	for(int i = n / T * T + 1;i <= n; ++ i)ans = mo(ans * i % p + ((i & 1) ? -1 : 1));
	cout << ans << '\n';
}


void table()
{
	int x = 1;//d(0) = 1，這個有點特殊
    cout << x << ",";
    int cnt = 1;
    for(int i = 1;i <= 1e9; ++ i)
    {
        x = x * i % p;
        if(i & 1)x = (x - 1 + p) % p;
        else x = (x + 1) % p;
        
        if(i % T == 0)
        {
        	cout << x << ",";
    		cnt ++;
    	}
    	
        if(cnt % 10 == 0)
        {
        	cout << '\n';
        	cnt = 1;
        }
        
    }
}

signed main()
{
    table();
	solve();
	//return 0;
}