C++，给定n和m，从1～n中随意挑出m个数，之后对选出的数排序，称为p。 小威想知道，排序后的序列p中，奇数位全为奇数，偶数位全为偶数的方案数，对998244353取模。 1≤m≤n≤1000000

<think>嗯，我现在需要解决这个问题。题目是说，给定n和m，从1到n中选出m个数，然后排序得到序列p。然后要满足奇数位全是奇数，偶数位全是偶数。这样的方案数对998244353取模。我得仔细想怎么解决这个问题。 首先，我得明确问题中的条件。排序后的序列p中，奇数位（也就是第1、3、5…位）必须都是奇数，偶数位（第2、4、6…位）必须都是偶数。那这里的奇偶位置是固定位置的奇偶性，还是根据排列后的位置来判断？比如，假设m是3，那么位置1和3必须是奇数，位置2必须是偶数？ 是的，题目中的“奇数位”和“偶数位”指的是序列的位置。例如，位置1、3、5等必须是奇数，位置2、4、6等必须是偶数。所以，对于选出的m个数，需要满足在排序后的序列中，每个位置上的数的奇偶性符合要求。 那我们需要将这些选出来的数分成奇数和偶数两部分，然后根据奇数和偶数的个数是否满足位置的要求来计算方案数。 首先，我需要确定在m个位置中有多少个奇数位和偶数位。假设总共有k个奇数位和t个偶数位。比如，当m是奇数时，奇数位的数量是(m+1)/2，偶数位是m/2。例如，m=3时，奇数位是位置1和3，共2个；偶数位是位置2，共1个。所以一般情况下，奇数位的数量是ceil(m/2)，即(m+1)//2，偶数位的数量是floor(m/2)，即m//2。 那假设奇数位的数量是k，偶数位的数量是t。那么k = (m+1)//2，t = m//2。接下来，我们需要从n个数中选出足够的奇数和偶数来满足这两个位置的需求。 首先，原问题中的数1~n中，奇数的个数是cnt_odd = (n+1)//2，偶数的个数是cnt_even = n//2。例如，n=5的话，奇数是1,3,5共3个，偶数是2,4共2个。 然后，我们需要选出k个奇数和t个偶数。如果选出来的奇数的数量不够k，或者偶数的数量不够t的话，这样的方案数就是0。所以，只有当cnt_odd >=k，并且cnt_even >=t时，才可能有解。否则，结果就是0。 所以，总的方案数是C(cnt_odd, k) * C(cnt_even, t)。其中C是组合数。然后，这些选出来的数需要被排序，奇数部分必须放在奇数位，偶数部分放在偶数位。并且，每个部分内部是有序的，因为整个序列p是排序后的结果。比如，选出来的奇数要按升序排列放在奇数位，选出来的偶数按升序排列放在偶数位。那么这种情况下，选出来的奇数和偶数的排列方式只有一种，因为已经排好序了。所以组合数的乘积就是方案数。 例如，假设k=2，t=1。那么选2个奇数和1个偶数。奇数的组合数是C(cnt_odd,2)，偶数是C(cnt_even,1)。总的方案数是它们的乘积。 所以，问题的答案应该是C( cnt_odd, k ) * C( cnt_even, t ) mod 998244353。其中k和t分别是需要的奇数和偶数的个数。 但是，需要考虑当k和t是否超过各自的可用数量的情况。如果cnt_odd <k或者 cnt_even <t的话，那么方案数是0。 所以，总的情况是： 当且仅当 cnt_odd >=k 且 cnt_even >=t 时，方案数是组合数的乘积，否则为0。 那如何计算组合数呢？因为n和m的范围是1e6，所以需要预处理阶乘和逆元，以快速计算组合数。 那问题的解决步骤是： 1. 预处理阶乘fact和逆元inv_fact，模数是998244353，范围到1e6。 2. 计算k = (m +1)//2，t = m//2. 3. 计算奇数的数量cnt_odd = (n +1)//2，偶数的数量cnt_even = n//2. 4. 如果cnt_odd <k 或者 cnt_even <t，则答案是0。 5. 否则，答案是 C(cnt_odd, k) * C(cnt_even, t) mod MOD. 那这样是否正确？ 比如，假设n=5，m=3。那么k=2，t=1. cnt_odd=3，cnt_even=2. 所以C(3,2)*C(2,1) =3*2=6. 那么这些可能的组合是： 奇数选两个，例如1,3；偶数选一个，比如2。然后排列后的序列是1,2,3。 或者选1,5和2，得到1,2,5；或者3,5和2，得到3,2,5？ 但排序后的序列是升序的，所以偶数必须放在偶数位，奇数的升序放在奇数位。比如，奇数选1和3，偶数选2，那么序列是1,2,3。如果偶数选4，那么是1,4,3？但3的位置是第三个位置，是奇数位，必须放奇数，所以没问题。那排序后的整个序列是按升序排列的，所以奇数位是升序，偶数位是升序吗？ 比如，假设选出的奇数是3和1，但排序后的奇数是1,3。所以整个序列p是排序后的结果，所以奇数位必须是升序，偶数位也是升序。所以组合数的乘积就是正确的方式。 所以，看来这个思路是正确的。 那现在的问题是，如何高效计算组合数C(a,b) mod MOD，其中a可以达到1e6，MOD是998244353，一个质数。 这个时候，预处理阶乘和逆元是可行的。预处理fact数组到1e6，然后inv_fact数组同样处理。然后组合数C(n, k) = fact[n] * inv_fact[k] * inv_fact[n-k] mod MOD。 那么，现在需要编写代码的思路。但是用户可能只需要数学上的解答，不过我需要确保这个思路的正确性。 有没有可能的错误？ 比如，当m=0的时候？但是题目中的条件给出1<=m<=n<=1e6，所以m至少是1。所以不需要考虑m=0的情况。 那另一个情况是，当k +t = m吗？因为k = (m+1)/2，当m为奇数时，比如m=3，k=2，t=1，总和是3。是的。当m是偶数时，比如m=4，k=2，t=2，总和是4。所以k +t等于m。所以没问题。 所以，这个思路是正确的。那么答案的计算就是正确的。 现在，我需要处理组合数的计算，预处理阶乘和逆元。对于n=1e6来说，这是可行的。 那现在，问题转化为，如何计算C(a, b) mod MOD，其中a最多是1e6，MOD是质数。 那MOD是998244353，是质数。所以可以用费马小定理求逆元。预处理阶乘和逆阶乘数组，时间复杂度是O(n)，可以处理到1e6。 综上，这个问题的解法是正确的，步骤是预处理阶乘和逆元，然后计算两种情况下的组合数相乘。</think>我们需要计算满足条件的方案数，即排序后的序列p中奇数位全为奇数，偶数位全为偶数。具体步骤如下： --- ### **分析条件** 1. **奇偶位置要求**：假设选出的序列长度为$m$，则： - 奇数位置数量为$k = \lceil \frac{m}{2} \rceil = \frac{m+1}{2}$（例如，$m=3$时，奇数位置为第1、3位，共2个）。 - 偶数位置数量为$t = \lfloor \frac{m}{2} \rfloor = \frac{m}{2}$（例如，$m=3$时，偶数位置为第2位，共1个）。 2. **数值范围**：在$1 \sim n$中： - 奇数总数为$\text{cnt\_odd} = \left\lceil \frac{n}{2} \right\rceil$。 - 偶数总数为$\text{cnt\_even} = \left\lfloor \frac{n}{2} \right\rfloor$。 3. **可行性判断**： - 若$\text{cnt\_odd} < k$或$\text{cnt\_even} < t$，则无解，方案数为0。 - 否则，需从奇数中选$k$个，偶数中选$t$个，组合数相乘。 --- ### **组合数计算** 1. **预处理阶乘与逆元**： - 定义模数$MOD = 998244353$，预处理阶乘数组$\text{fact}[i] = i! \mod MOD$。 - 预处理逆元数组$\text{inv\_fact}[i] = (i!)^{-1} \mod MOD$，通过费马小定理计算。 2. **组合数公式**： - $C(a, b) = \text{fact}[a] \cdot \text{inv\_fact}[b] \cdot \text{inv\_fact}[a-b] \mod MOD$。 --- ### **具体步骤** 1. 计算$k = \frac{m+1}{2}$和$t = \frac{m}{2}$。 2. 计算$\text{cnt\_odd}$和$\text{cnt\_even}$。 3. 若$\text{cnt\_odd} \geq k$且$\text{cnt\_even} \geq t$，则答案为： $$ \text{ans} = C(\text{cnt\_odd}, k) \cdot C(\text{cnt\_even}, t) \mod 998244353 $$ 4. 否则，答案为0。 --- ### **代码实现（关键部分）** ```cpp #include <bits/stdc++.h> using namespace std; const int MOD = 998244353; const int MAX = 1e6 + 5; // 预处理阶乘和逆元 long long fact[MAX], inv_fact[MAX]; long long power(long long a, long long b) { long long res = 1; while (b) { if (b % 2) res = res * a % MOD; a = a * a % MOD; b /= 2; } return res; } void precompute() { fact[0] = 1; for (int i = 1; i < MAX; i++) { fact[i] = fact[i-1] * i % MOD; } inv_fact[MAX-1] = power(fact[MAX-1], MOD-2); for (int i = MAX-2; i >= 0; i--) { inv_fact[i] = inv_fact[i+1] * (i+1) % MOD; } } long long C(int a, int b) { if (a < 0 || b < 0 || a < b) return 0; return fact[a] * inv_fact[b] % MOD * inv_fact[a - b] % MOD; } int main() { precompute(); int n, m; cin >> n >> m; int k = (m + 1) / 2; // 奇数位数量 int t = m / 2; // 偶数位数量 int cnt_odd = (n + 1) / 2; int cnt_even = n / 2; if (cnt_odd >= k && cnt_even >= t) { long long ans = C(cnt_odd, k) * C(cnt_even, t) % MOD; cout << ans << endl; } else { cout << 0 << endl; } return 0; } ``` --- ### **复杂度分析** - **时间复杂度**：预处理阶乘和逆元为$O(n)$，每次查询为$O(1)$。 - **空间复杂度**：$O(n)$，用于存储阶乘和逆元数组。