集美
分析:
一道组合计数,不过正着想有很多重复的情况,这里我们选择从非法方案着手考虑
因为 gcd(a, b) 为偶数就合法,那么在奇数位置上放偶数一定不合法,我们考虑奇数位置的方案
- n 为偶数,就会有偶数个偶数和偶数个奇数,在奇数位置上排列偶数,在偶数位置上排列奇数,即总的非法方案数
- n 为奇数,奇数位置就会比偶数位置多一个,现将所有偶数在奇数位置上全排列,再选择一个奇数放在多出来的一个奇数位置上,剩余的奇数在偶数位置上全排列
有总方案为 n 个数的全排列,即可算出合法方案
实现:
#include <bits/stdc++.h>
using namespace std;
#define mst(x, y) memset(x, y, sizeof x)
#define endl '\n'
#define INF LONG_LONG_MAX
#define int long long
#define Lson u << 1, l, mid
#define Rson u << 1 | 1, mid + 1, r
#define FAST ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
const int N = 2000010, MOD = 1e9 + 7;
const double EPS = 1e-6;
typedef pair<int, int> PII;
typedef unordered_map<int, int> Ump;
int T;
int n;
int res;
int fact[N];
int qmi(int a, int b)
{
int res = 1;
while (b)
{
if (b & 1)
res = res * a % MOD;
a = a * a % MOD;
b >>= 1;
}
return res;
}
void init()
{
fact[0] = 1;
for (int i = 1; i < N; i++)
fact[i] = fact[i - 1] * i % MOD;
}
void solve()
{
cin >> n;
res = fact[n];
int del;
if (n & 1)
del = (n + 1) / 2 * fact[n / 2] % MOD * fact[(n + 1) / 2] % MOD;
else
del = fact[n / 2] * fact[n / 2] % MOD;
res = (res - (del % MOD) + MOD) % MOD;
cout << res << endl;
}
signed main()
{
FAST;
T = 1;
// cin >> T;
init();
while (T--)
solve();
return 0;
}
标签:这里,奇数,没有,res,偶数,int,集美,fact,MOD
From: https://www.cnblogs.com/Aidan347/p/17274297.html