题目
题目描述
**YZ（已被和谐）的食堂实在是太挤辣！所以Apojacsleam现在想邀请他的一些好友去校外吃一顿饭，并在某酒店包下了一桌饭。
当Apojacsleam和他的同学们来到酒店之后，他才发现了这些同学们其实是N对cp，由于要保护广大单身狗的弱小心灵（FF！），所以他不想让任意一对情侣相邻。
说明：
·酒店的桌子是恰好有2N个位置的圆桌。
·客人恰好是N对cp，也就是说，圆桌上没有空位。
·桌子的每一个位置是一样的，也就是说，如果两种方案可以通过旋转得到，那么这就可以视为相等的。
现在，你需要求出，将任意一对情侣不相邻的方案数。
输入描述
一行一个正整数N，表示cp的对数。
输出描述
一行一个非负整数，表示答案对1000000007取模后的值。
示例1
输入
2
输出
2
说明
两种方案：
假设1-2、3-4是两对情侣。
方案有1-3-2-4
1-4-2-3
或者你也可以认为1-3-2-4
2-3-1-4
是合法的方案。
示例2
输入
25
输出
535659175
示例3
输入
1000000
输出
270258012
说明
对于20%的数据，1<=N<=5
对于30%的数据，1<=N<=20
对于50%的数据，1<=N<=100
对于70%的数据，1<=N<=200000
对于100%的数据，1<=N<=30000000
题解
方法一
知识点：容斥原理，排列组合。
考虑容斥原理求出至少有一对cp坐在一起的方案数，最后用圆全排列减去方案数即可。
容易得到，至少有 \(i\) 对cp坐在一起的方案数：
于是我们可以线性求出答案：
但这道题卡空间，注意到组合数只需要到 \(n\) 就行。
为了不需要快速幂求阶乘逆元，我们从 \(n\) 逆推，过程中处理阶乘。同时，我们可以直接使用 \(2\) 的逆元 \(\dfrac{1+P}{2}\)。
时间复杂度 \(O(n)\)
空间复杂度 \(O(n)\)
方法二
知识点：计数dp。
因为cp是成对的，我们先取 \(n\) 对cp的其中一人安排到排列里，在考虑将剩下 \(n\) 个人往里面插入。
不妨先假设前 \(n\) 个人已经排好，考虑设 \(f_i\) 表示插入了剩下的人中前 \(i\) 个人的排列数。
考虑 \(f_i\) ，即已经插了 \(i-1\) 个人，准备插第 \(i\) 个人。转移方程有两种情况：
- 直接往前插入，只需要保证插入的左右不是自己的cp即可，总方案数为 \((n+i-3)f_{i-1}\) 。
- 插入到前面某一个人与他cp中间，因为cp相邻本身是不合法的，所以之前不可能存在这种方案，但我们可以插入到某个不合法的cp之间，这种方案就合法了，所以需要额外考虑。前面共有 \(i-1\) 个人，可以在cp的左边和右边两种情况，因此总方案数为 \(2(i-1)f_{i-2}\) 。
所以 \(f_i = (n+i-3)f_{i-1} + 2(i-1)f_{i-2}\) 。
可以考虑只保留前面两项的值，省空间。
时间复杂度 \(O(n)\)
空间复杂度 \(O(1)\)
代码
方法一
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int P = 1e9 + 7;
namespace Number_Theory {
const int N = 6e7 + 7;
int qpow(int a, ll k) {
int ans = 1;
while (k) {
if (k & 1) ans = 1LL * ans * a % P;
k >>= 1;
a = 1LL * a * a % P;
}
return ans;
}
int fact[N], invfact[N];
void init(int n) {
fact[0] = 1;
for (int i = 1;i <= n;i++) fact[i] = 1LL * i * fact[i - 1] % P;
invfact[n] = qpow(fact[n], P - 2);
for (int i = n;i >= 1;i--) invfact[i - 1] = 1LL * invfact[i] * i % P;
}
}
namespace CNM {
using namespace Number_Theory;
int C(int n, int m) {
if (n == m && m == -1) return 1; //* 隔板法特判
if (n < m || m < 0) return 0;
return 1LL * fact[n] * invfact[n - m] % P * invfact[m] % P;
}
}
/// 公式法求组合数，O(n)，预处理阶乘及其逆元快速求出组合数
using namespace CNM;
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n;
cin >> n;
if (n == 1) {
cout << 0 << '\n';
return 0;
}
Number_Theory::init(n);
int ans = 0, pow2 = qpow(2, n), fac = fact[n - 1];
for (int i = n;i >= 0;i--) {
(ans += (i & 1 ? -1LL : 1LL) * pow2 * C(n, i) % P * fac % P) %= P;
(ans += P) %= P;
pow2 = (1LL + P) / 2 * pow2 % P;
fac = 1LL * fac * (n - i + n) % P;
}
cout << ans << '\n';
return 0;
}
方法二
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int P = 1e9 + 7;
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n;
cin >> n;
if (n == 1) {
cout << 0 << '\n';
return 0;
}
int f0 = 1, f1 = n - 2;// 前n个人不是cp随便排，考虑后n个人的前i个往前插的方案数
for (int i = 2;i <= n;i++) {
f0 = (1LL * f1 * (n + i - 3) % P + 1LL * f0 * (i - 1) * 2 % P) % P;
// 直接往前插有n-i-3种方案，选前i-1个人中的一个并在他和他cp中间挡着有(i-1)*2中方案
swap(f0, f1);
}
int ans = f1;
for (int i = 1;i <= n - 1;i++) ans = 1LL * ans * i % P;
cout << ans << '\n';
return 0;
}