HJ143 小红的好排列

• 题目
• 题解(18)
• 讨论(8)
• 排行

较难 通过率：29.30% 时间限制：1秒 空间限制：256M

知识点数论

校招时部分企业笔试将禁止编程题跳出页面，为提前适应，练习时请使用在线自测，而非本地IDE。

描述

小红认为一个偶数长度为 nn 的排列{a1,a2,…,an}{a1​,a2​,…,an​} 是好排列，当且仅当恰好有一半的 ii 使得 ai×iai​×i 是 33 的倍数。
小红想知道，全部长度为 nn 的排列中，共有多少个好排列？由于答案可能很大，请将答案对 (109+7)(109+7) 取模后输出。

长度为 nn 的排列是由 1∼n1∼n 这 nn 个整数、按任意顺序组成的数组，其中每个整数恰好出现一次。例如，{2,3,1,5,4}{2,3,1,5,4} 是一个长度为 55 的排列，而 {1,2,2}{1,2,2} 和 {1,3,4}{1,3,4} 都不是排列，因为前者存在重复元素，后者包含了超出范围的数。

输入描述：

在一行上输入一个正偶数 n(2≦n≦106)n(2≦n≦106) 代表排列中的元素数量。

输出描述：

输出一个整数，代表好排列的数量。由于答案可能很大，请将答案对 (109+7)(109+7) 取模后输出。

示例1

输入：

2

复制输出：

0

复制说明：

在这个样例中，长度为 22 的排列有且仅有两个： ∙ ∙{1,2}{1,2}，第一个元素 11 使得 1×1=11×1=1，第二个元素 22 使得 2×2=42×2=4，均不是 33 的倍数； ∙ ∙{2,1}{2,1}，同理。 因此，长度为 22 的排列中，不存在好排列。

示例2

输入：

4

复制输出：

18

复制说明：

在这个样例中，一共有 1818 个长度为 44 的排列满足条件，例如： ∙ ∙{1,2,4,3}{1,2,4,3}，第一个元素 11 使得 1×1=11×1=1，第二个元素 22 使得 2×2=42×2=4，第三个元素 44 使得 4×3=124×3=12，第四个元素 33 使得 3×4=123×4=12，恰好有一半的 ii 使得 ai×iai​×i 是 33 的倍数。

#include <bits/stdc++.h> #define x first #define y second using namespace std; typedef long long LL; typedef pair<int, int> PII; const int N = 1e6 + 10, MOD = 1e9 + 7; const LL INF = 1e18; int n; LL fact[N], infact[N]; LL q_pow(LL a, LL b) { a %= MOD; LL ans = 1; while (b) { if (b & 1) ans = ans * a % MOD; a = a * a % MOD; b >>= 1; } return ans; } void init() { infact[0] = fact[0] = 1; for (int i = 1; i < N; ++i) { fact[i] = fact[i - 1] * i % MOD; infact[i] = q_pow(fact[i], MOD - 2); } } LL C(LL a, LL b) { if (a < b || b < 0) return 0; return fact[a] * infact[a - b] % MOD * infact[b] % MOD; } int main() { ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); init(); cin >> n; int m = n / 3; int k = 2 * m - n / 2; if (k < 0 || k > m) { cout << 0 << '\n'; return 0; } LL ans = C(m, k) * C(n - m, m - k) % MOD * fact[m] % MOD * fact[n - m] % MOD; cout << ans << '\n'; return 0; }