(large{题目链接})
(\)
题意：
某人写了(n)封信和(n)个信封，如果所有的信都装错了信封。求所有信都装错信封共有多少种不同情况。
思路：
1.依据递推公式：(D_n = (n-1) imes (D_{n-1} +D_{n-2}))
2.学习二项式反演发现这题也可以用这个做。
首先二项式反演的公式是：(f_{n}=sum limits^{n}_{i=0}left( -1
ight) ^{i}egin{pmatrix}
n \
i
end{pmatrix}g_{i} Leftrightarrow g_{n}=sum limits^{n}_{i=0}left( -1
ight) ^{i}egin{pmatrix}
n \
i
end{pmatrix}f_{i})
更常用的式子是(f_{n}=sum limits^{n}_{i=0}egin{pmatrix}
n \
i
end{pmatrix}g_{i}Leftrightarrow g_{n}=sum limits^{n}_{i=0}left( -1
ight) ^{n-i}egin{pmatrix}
n \
i
end{pmatrix}f_{i})
回归这个题，我们知道(n)个信的排列的方案数是(n!)。
设(f_i)表示有(i)恰好有(i)个位置改变的排列个数，那么(n)个的排列总数就是(i = 0,1,...,n-1,n)的和，即(n! = sum limits^{n}_{i=0}egin{pmatrix}
n \
i
end{pmatrix}f_{i})，观察这个式子，与刚刚的反演式子很相似，这里的(n!)就是(g_n)。
那么利用二项式反演公式可以得到：
[f_n = sum limits^{n}_{i=0}left( -1
ight) ^{i+n}egin{pmatrix}
n \
i
end{pmatrix}f_{i}]
[=n!sum limits^{n}_{i=0}dfrac {left( -1
ight) ^{i}}{i!}
]
由于没有逆元，所以把(n!)提进去。
代码：
#include <bits/stdc++.h>
typedef long long ll;
int main() {
ll fac[23];
fac[0] = fac[1] = 1;
for (int i = 2; i <= 20; ++i) fac[i] = fac[i - 1] * i;
int n;
std::cin >> n;
ll ans = 0;
for (int i = 0; i <= n; ++i) ans += (i & 1) ? -(fac[n] / fac[i]) : fac[n] / fac[i];
std::cout << ans;
return 0;
}