共计 3058 个字符，预计需要花费 8 分钟才能阅读完成。
题目链接：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;
}