选课 / T3
题目大意
给你 n 个位置 n 个数，第 i 个不能放在第 i 个位置和第 i+1 个位置（如果 i 是 n 就是第 n 个和第 1 个）
给你 n，要你求放的方案数。
思路
不难这是一个环之类的，考虑先弄序列的。
你把每个数不能放的位置列出来。
((1,2),(2,3),(3,4),(4,5),...)
感觉搞不能放的很麻烦，考虑正难则反，考虑求至少有 (k) 个不合法的有多少情况。
然后搞出来正反正反容斥一下即可。
然后你考虑怎么求至少有 (k) 个不合法的。
你考虑从前面列出来的东西来搞，考虑在这些括号里面选 (k) 个括号里面选一个，而且选的都是要不同的数。
那不难想到括号内的两个数不能同时选，相同的两个数也不能同时选。（相同的数是隔着括号相邻的）
那总的来说，把括号删掉，就变成了不能选相邻的数！
那问题就变成了在 (2n) 个数中选 (k) 个，不能选相邻的数。
那你考虑插板法，在 (2n-k) 个数的间隙中插入板，插入 (k) 个板，那就是 (C_{2n-k+1}^k)。
然后考虑从序列变成环，要怎么搞。
考虑破环为链，那破的地方有 (2n) 个，所以搞出来的方案数要乘 (2n)。
然后第一个数的前面和最后一个数的后面是同一个间隙，所以间隙少了一个，就是 (C_{2n-k}^k)。
但是断开的地方可能也被当乘了间隙，而它应该是最前面和最后面那个共同的间隙，而选到这个的只有一种情况，而一共有 (2n-k) 个间隙，所以这个概率是 (dfrac{1}{2n-k})，答案要乘上。
那剩下的都是任选，就是 ((n-k)!)。
那总的来说，要至少有 (k) 个不合法，它的方案数就是：
(dfrac{C_{2n-k}^k*2n}{2n-k}*(n-k)!)
化简一下，就是：
(dfrac{2n(n-k)!(2n-k-1)!}{k!(2n-2k)!})
然后预处理阶乘和它的逆元，就可以 (O(nq)) 求了。
（然而这题有阴间的递推式，鬼知道要怎么算出来，好像也没有讲怎么搞出来的，都是打标用电脑找规律，就不用了）
代码
#include<cstdio>
#define ll long long
#define mo 1000000007
using namespace std;
int n;
ll jc[200001], inv[200001], ans, op;
ll ksm(ll x, ll y) {
ll re = 1;
while (y) {
if (y & 1) re = (re * x) % mo;
x = (x * x) % mo;
y >>= 1;
}
return re;
}
ll W(int k, int n) {
return jc[2 * n - k - 1] * jc[n - k] % mo * (2 * n) % mo * inv[k] % mo * inv[2 * n - 2 * k] % mo;
}
int main() {
jc[0] = 1;//预处理
for (int i = 1; i <= 200000; i++) jc[i] = jc[i - 1] * i % mo;
inv[200000] = ksm(jc[200000], mo - 2);
for (int i = 200000 - 1; i >= 0; i--)
inv[i] = inv[i + 1] * (i + 1) % mo;
while (scanf("%d", &n) != EOF) {
if (n <= 2) printf("0
");
else {
ans = jc[n];
op = -1;//直接套公式，容斥算
for (int i = 1; i <= n; i++, op = -op) {
ans = (ans + (op * W(i, n))) % mo;
if (ans < 0) ans += mo;
}
printf("%lld
", ans);
}
}
return 0;
}