![[ACM组合数学 | 错排公式]写信](/static/background/42.jpg "[ACM组合数学 | 错排公式]写信")
题意很简单，但是数据范围偏大。
错排公式
\[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; ++ ians = 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 & 1x = (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;
}