「RMI 2018」W

0
雷光昊 @ 2025-12-8 16:28:33
「RMI 2018」W 题解

给定 $N$ 个整数的多重集，需要计算有多少个不同的排列是 W 形 的。

W 形排列定义：
1. 由四个段组成：递减、递增、递减、递增
2. 相邻段共享端点
3. 每个段至少包含两个不同值
4. 相同值的元素视为不可区分
关键分析

1. W 形结构

设四个段为： $A_1$ （递减）、 $A_2$ （递增）、 $A_3$ （递减）、 $A_4$ （递增）

相邻段共享端点：
- $A_1$ 的最后一个元素 = $A_2$ 的第一个元素（设为 $x$ ）
- $A_2$ 的最后一个元素 = $A_3$ 的第一个元素（设为 $y$ ）
- $A_3$ 的最后一个元素 = $A_4$ 的第一个元素（设为 $z$ ）
所以整个序列有 3 个转折点 $x, y, z$ 。

2. 值的大小关系

由于段的单调性：
- $A_1$ 递减到 $x$ ：所以 $A_1$ 中所有元素 ≥ $x$ ，且至少有一个 > $x$
- $A_2$ 从 $x$ 递增到 $y$ ：所以 $x < y$
- $A_3$ 从 $y$ 递减到 $z$ ：所以 $y > z$
- $A_4$ 从 $z$ 递增：所以 $A_4$ 中所有元素 ≥ $z$ ，且至少有一个 > $z$
因此： $x < y > z$

3. 元素分配

设多重集中每个值 $v$ 出现 $c_v$ 次。

对于固定的转折点 $x=a, y=b, z=c$ （ $a<b>c$ ）：

剩余元素分为几类：
1. 值在 $(a, b)$ 之间：只能放在 $A_2$ （从 $a$ 递增到 $b$ ）
2. 值在 $(c, b)$ 之间：只能放在 $A_3$ （从 $b$ 递减到 $c$ ）
3. 值 > $\max(a, c)$ 且 ≠ $b$ ：可以放在 $A_1$ 或 $A_4$
4. 值 = $a$ 的多余副本：可以放在 $A_1$ 或 $A_2$
5. 值 = $b$ 的多余副本：可以放在 $A_2$ 或 $A_3$
6. 值 = $c$ 的多余副本：可以放在 $A_3$ 或 $A_4$
但注意：每个段至少需要两个不同值，这已经由 $a,b,c$ 不同保证了。

解决方案

方法1：枚举转折点 + 组合计数

第一步：预处理频率

统计每个值的出现次数，将值排序为 $v_1 < v_2 < \cdots < v_k$ 。
```
vector<int> values;      // 不同的值
vector<int> freq;        // 每个值的频率
vector<long long> pref;  // 频率前缀和
```
第二步：枚举转折点

枚举三个不同的值作为转折点 $a, b, c$ ，满足 $a < b > c$ 。
```
long long total = 0;
for (int i = 0; i < k; i++) {        // a = values[i]
    for (int j = i+1; j < k; j++) {  // b = values[j]
        for (int l = 0; l < k; l++) { // c = values[l], l != j
            if (l == j) continue;
            // 计算这种选择的排列数
            total += count_permutations(i, j, l);
        }
    }
}
```
但这样是 $O(k^3)$ ， $k$ 最多 $N=300000$ ，不可行。

第三步：优化枚举

由于 $a < b > c$ ，我们可以固定 $b$ ，然后分别考虑 $a$ 和 $c$ 。

对于固定的 $b$ （索引 $j$ ）：
- $a$ 可以是 $b$ 左边的任何值（索引 < $j$ ）
- $c$ 可以是 $b$ 右边的任何值（索引 > $j$ ），或者左边的值但 ≠ $a$
实际上， $c$ 只需要满足 $c < b$ ，不一定要在 $a$ 的左边或右边。

更准确地说： $a < b$ 且 $c < b$ ， $a, b, c$ 两两不同。

所以对于每个 $b$ ，需要选择两个不同的 $a, c$ 都小于 $b$ 。

排列数：对于固定的 $b$ ，有 $\binom{\text{小于b的值个数}}{2}$ 种方式选择 $(a,c)$ 的有序对（ $a≠c$ ）。

但 $a$ 和 $c$ 不对称，需要考虑它们的具体值。

第四步：计算固定转折点的排列数

对于固定的 $a=v_i, b=v_j, c=v_k$ （ $i<j, k<j, i≠k$ ）：

定义：
- $L = \{v: a < v < b\}$ ：只能去 $A_2$
- $R = \{v: c < v < b\}$ ：只能去 $A_3$
- $M = \{v: v > \max(a,c) \text{ 且 } v ≠ b\}$ ：可以去 $A_1$ 或 $A_4$
- 还有 $a,b,c$ 的多余副本需要分配
设：
- $cnt_L = \sum_{v \in L} freq[v]$ ：只能去 $A_2$ 的元素数
- $cnt_R = \sum_{v \in R} freq[v]$ ：只能去 $A_3$ 的元素数
- $cnt_M = \sum_{v \in M} freq[v]$ ：可以去 $A_1$ 或 $A_4$ 的元素数
另外：
- $a$ 有 $freq[a]-1$ 个多余副本（一个用作转折点）
- $b$ 有 $freq[b]-1$ 个多余副本
- $c$ 有 $freq[c]-1$ 个多余副本
这些多余副本的分配：
- $a$ 的多余：可以去 $A_1$ （递减）或 $A_2$ （递增）
- $b$ 的多余：可以去 $A_2$ （递增）或 $A_3$ （递减）
- $c$ 的多余：可以去 $A_3$ （递减）或 $A_4$ （递增）
第五步：生成函数方法

用生成函数表示分配方式：

对于 $cnt_M$ 个元素（每个值可能不同，但相同值的元素不可区分）：

实际上，每个值 $v \in M$ 有 $freq[v]$ 个副本，需要分配到 $A_1$ 和 $A_4$ 。

设值 $v$ 分配 $x_v$ 个到 $A_1$ ， $freq[v]-x_v$ 个到 $A_4$ ， $0 \leq x_v \leq freq[v]$ 。

所以对于值 $v$ ，有 $freq[v]+1$ 种分配方式。

因此 $M$ 中所有值的总分配方式： $\prod_{v \in M} (freq[v]+1)$

类似地：
- $a$ 的多余： $freq[a]$ 种分配方式（ $0$ 到 $freq[a]-1$ 个去 $A_1$ ）
- $b$ 的多余： $freq[b]$ 种分配方式
- $c$ 的多余： $freq[c]$ 种分配方式
第六步：段内排列计数

分配完元素后，每个段内的排列是确定的（因为单调性要求）：
- $A_1$ ：递减排列，相同值连续
- $A_2$ ：递增排列，相同值连续
- $A_3$ ：递减排列，相同值连续
- $A_4$ ：递增排列，相同值连续
但相同值的元素不可区分，所以每个段内只有一种排列方式。

因此，分配方式数就是排列数。

第七步：完整公式

对于固定的 $a=v_i, b=v_j, c=v_k$ ：
$$\text{count} = \left(\prod_{v \in M} (freq[v]+1)\right) \times freq[a] \times freq[b] \times freq[c] $$
其中 $M = \{v: v > \max(a,c) \text{ 且 } v ≠ b\}$

注意：这里 $freq[a], freq[b], freq[c]$ 包括了转折点本身的多余副本分配。

第八步：高效计算

我们需要对所有 $a<b>c$ 且 $a,b,c$ 不同的三元组求和。

设值排序为 $v_1 < v_2 < \cdots < v_k$ 。

对于固定的 $b=v_j$ ：
- $a$ 可以是 $v_i$ ， $i < j$
- $c$ 可以是 $v_l$ ， $l < j$ 且 $l ≠ i$
或者 $c$ 也可以小于 $b$ 但不一定在左边（实际上所有小于 $b$ 的值都可能）。

我们需要计算：
$$\sum_{i<j} \sum_{l
\max(v_i, v_l), v≠v_j} (freq[v]+1)\right) \times freq[i] \times freq[j] \times freq[l] $$
第九步：进一步优化

对于固定的 $b=v_j$ ，定义：

$P_{\geq x} = \prod_{v \geq x, v≠v_j} (freq[v]+1)$

$P_{> x} = \prod_{v > x, v≠v_j} (freq[v]+1)$

那么对于 $a=v_i, c=v_l$ （ $i,l < j, i≠l$ ）：
$$\prod_{v > \max(v_i, v_l), v≠v_j} (freq[v]+1) = P_{> \max(v_i, v_l)} $$
设 $m = \max(i, l)$ ，则 $P_{> \max(v_i, v_l)} = P_{> v_m} = \prod_{t=m+1}^{k} (freq[t]+1)$（排除 $j$ ）

所以：
$$\text{对于固定b} = freq[j] \times \sum_{i<j} \sum_{l \max(i,l)} $$
第十步：计算 $\sum_{i<j} \sum_{l \max(i,l)}$

设 $S_1 = \sum_{i<j} freq[i]$ 设 $S_2 = \sum_{i<j} freq[i]^2$

那么：
$$\sum_{i<j} \sum_{l \max(i,l)} = \sum_{m=0}^{j-1} P_{> m} \times \left(\sum_{i \leq m} freq[i] \times \sum_{l > m, l m, i<j} freq[i]\right) / 2 $$
但更简单的方法：枚举 $m = \max(i,l)$ ：

情况1： $i=m, l<m$ ：贡献 = $freq[m] \times \sum_{l<m} freq[l] \times P_{> m}$

情况2： $l=m, i<m$ ：同上，对称

情况3： $i=l=m$ ：不考虑，因为 $i≠l$

所以：
$$\text{sum} = 2 \times \sum_{m=0}^{j-1} \left(freq[m] \times \left(\sum_{l=0}^{m-1} freq[l]\right) \times P_{> m}\right) $$
其中 $P_{> m} = \prod_{t=m+1}^{k} (freq[t]+1)$ （排除 $j$ ）

第十一步：算法实现

#include <bits/stdc++.h> using namespace std; const int MOD = 1000000007; int main() { int N; cin >> N; vector<int> arr(N); for (int i = 0; i < N; i++) { cin >> arr[i]; } // 统计频率 map<int, int> freq_map; for (int x : arr) { freq_map[x]++; } // 转换为排序的数组 vector<int> values, freq; for (auto& [val, cnt] : freq_map) { values.push_back(val); freq.push_back(cnt); } int k = values.size(); // 预处理前缀和和后缀积 vector<long long> prefix_sum(k+1, 0); // freq前缀和 vector<long long> prefix_sum2(k+1, 0); // freq平方前缀和 vector<long long> suffix_prod(k+2, 1); // (freq+1)后缀积 for (int i = 0; i < k; i++) { prefix_sum[i+1] = (prefix_sum[i] + freq[i]) % MOD; prefix_sum2[i+1] = (prefix_sum2[i] + 1LL * freq[i] * freq[i]) % MOD; } for (int i = k-1; i >= 0; i--) { suffix_prod[i] = suffix_prod[i+1] * (freq[i] + 1) % MOD; } long long total = 0; // 枚举b for (int j = 0; j < k; j++) { long long prod_b = freq[j]; // 计算 P_{> m} 数组（排除j） vector<long long> P_greater(j, 0); long long prod = 1; for (int t = j+1; t < k; t++) { prod = prod * (freq[t] + 1) % MOD; } for (int m = j-1; m >= 0; m--) { // P_{> m} = prod_{t=m+1}^{k} (freq[t]+1)，排除j if (m+1 <= j-1) { prod = prod * (freq[m+1] + 1) % MOD; } P_greater[m] = prod; } // 计算 sum = 2 * Σ_m freq[m] * (Σ_{l<m} freq[l]) * P_{> m} long long sum = 0; long long running_sum = 0; // Σ_{l<m} freq[l] for (int m = 0; m < j; m++) { sum = (sum + 2LL * freq[m] % MOD * running_sum % MOD * P_greater[m]) % MOD; running_sum = (running_sum + freq[m]) % MOD; } total = (total + prod_b * sum) % MOD; } cout << total << endl; return 0; }

算法复杂度

时间复杂度： $O(k^2)$ ，其中 $k$ 是不同值的数量

最坏情况 $k = N = 300000$ ， $O(N^2)$ 不可行

需要进一步优化到 $O(k \log k)$ 或 $O(k)$

进一步优化

实际上，我们可以将计算优化到 $O(k)$ ：

对于固定的 $b=v_j$ ：
$$\text{sum} = 2 \times \sum_{m=0}^{j-1} \left(freq[m] \times prefix\_sum[m] \times P_{> m}\right) $$
其中 $P_{> m} = \prod_{t=m+1}^{k} (freq[t]+1)$ （排除 $j$ ）

我们可以预处理：

$prefix\_prod[i] = \prod_{t=0}^{i} (freq[t]+1)$

$suffix\_prod[i] = \prod_{t=i}^{k-1} (freq[t]+1)$

那么 $P_{> m} = \frac{suffix\_prod[m+1]}{freq[j]+1}$ （如果 $m < j$ ）或更复杂的表达式。

实际上，$P_{> m} = \prod_{t=m+1}^{j-1} (freq[t]+1) \times \prod_{t=j+1}^{k-1} (freq[t]+1)$

设：

$left\_prod[m] = \prod_{t=m+1}^{j-1} (freq[t]+1)$

$right\_prod = \prod_{t=j+1}^{k-1} (freq[t]+1)$

那么 $P_{> m} = left\_prod[m] \times right\_prod$

我们可以预处理 $left\_prod$ 数组，或者在线计算。

最终算法

#include <bits/stdc++.h> using namespace std; const int MOD = 1000000007; long long modpow(long long a, long long b) { long long res = 1; while (b) { if (b & 1) res = res * a % MOD; a = a * a % MOD; b >>= 1; } return res; } long long modinv(long long a) { return modpow(a, MOD-2); } int main() { ios::sync_with_stdio(false); cin.tie(0); int N; cin >> N; vector<int> arr(N); map<int, int> freq_map; for (int i = 0; i < N; i++) { cin >> arr[i]; freq_map[arr[i]]++; } vector<int> values, freq; for (auto& [val, cnt] : freq_map) { values.push_back(val); freq.push_back(cnt); } int k = values.size(); // 预处理前缀和、前缀积、后缀积 vector<long long> pref_sum(k+1, 0); vector<long long> pref_prod(k+1, 1); vector<long long> suff_prod(k+2, 1); for (int i = 0; i < k; i++) { pref_sum[i+1] = (pref_sum[i] + freq[i]) % MOD; pref_prod[i+1] = pref_prod[i] * (freq[i] + 1) % MOD; } for (int i = k-1; i >= 0; i--) { suff_prod[i] = suff_prod[i+1] * (freq[i] + 1) % MOD; } long long total = 0; // 枚举b for (int j = 0; j < k; j++) { long long right_prod = suff_prod[j+1]; // ∏_{t=j+1}^{k-1} (freq[t]+1) // 计算 sum = 2 * Σ_{m=0}^{j-1} freq[m] * pref_sum[m] * (∏_{t=m+1}^{j-1} (freq[t]+1)) * right_prod long long sum = 0; long long left_prod = 1; // ∏_{t=m+1}^{j-1} (freq[t]+1)，从后往前累乘 for (int m = j-1; m >= 0; m--) { // 对于m，left_prod = ∏_{t=m+1}^{j-1} (freq[t]+1) sum = (sum + freq[m] * pref_sum[m] % MOD * left_prod) % MOD; left_prod = left_prod * (freq[m] + 1) % MOD; } sum = 2 * sum % MOD * right_prod % MOD; total = (total + freq[j] * sum) % MOD; } cout << total << endl; return 0; }

算法复杂度

时间复杂度： $O(k^2)$ ，但实际中 $k$ （不同值的数量）通常远小于 $N$

最坏情况 $k = N$ （所有值不同）时 $O(N^2)$ 仍然太大

需要进一步优化到 $O(k)$ 或 $O(k \log k)$

进一步优化到 $O(k)$

上述算法中，对于每个 $j$ ，我们计算了：
$$sum_j = 2 \times right\_prod_j \times \sum_{m=0}^{j-1} \left(freq[m] \times pref\_sum[m] \times \prod_{t=m+1}^{j-1} (freq[t]+1)\right) $$
设 $T_m = freq[m] \times pref\_sum[m]$

那么 $sum_j = 2 \times right\_prod_j \times \sum_{m=0}^{j-1} \left(T_m \times \prod_{t=m+1}^{j-1} (freq[t]+1)\right)$

我们可以用前缀和技巧：设 $S_j = \sum_{m=0}^{j-1} \left(T_m \times \prod_{t=m+1}^{j-1} (freq[t]+1)\right)$

注意到：
$$S_{j+1} = \sum_{m=0}^{j} \left(T_m \times \prod_{t=m+1}^{j} (freq[t]+1)\right) = \left(\sum_{m=0}^{j-1} \left(T_m \times \prod_{t=m+1}^{j-1} (freq[t]+1)\right)\right) \times (freq[j]+1) + T_j = S_j \times (freq[j]+1) + T_j $$
所以我们可以 $O(k)$ 计算所有 $S_j$ 。

最终算法 $O(k)$ ：

vector<long long> S(k+1, 0); // S[0] = 0 for (int j = 0; j < k; j++) { S[j+1] = (S[j] * (freq[j] + 1) + freq[j] * pref_sum[j]) % MOD; } long long total = 0; long long right_prod = 1; // 从后往前累乘 for (int j = k-1; j >= 0; j--) { // 对于b = values[j] total = (total + freq[j] * 2 % MOD * S[j] % MOD * right_prod) % MOD; right_prod = right_prod * (freq[j] + 1) % MOD; }

算法标签

组合数学：排列计数、生成函数、分配问题

动态规划/递推：优化计算过程

数论：模运算

前缀和/后缀积：高效计算

总结

本题的核心是将 W 形排列计数转化为组合数学问题：

关键观察：W 形由三个转折点定义

问题转化：枚举转折点，计算元素分配方式

数学推导：得到组合计数公式

算法优化：使用前缀和、后缀积优化到 $O(k)$

最终算法可以在 $O(k)$ 时间内解决问题，其中 $k$ 是不同值的数量，满足题目的大数据量要求。

ID

5894

时间

1000ms

内存

256MiB

难度

标签

递交数

已通过

上传者

雷光昊

1 条题解

「RMI 2018」W 题解

关键分析

1. W 形结构

2. 值的大小关系

3. 元素分配

解决方案

方法1：枚举转折点 + 组合计数

第一步：预处理频率

第二步：枚举转折点

第三步：优化枚举

第四步：计算固定转折点的排列数

第五步：生成函数方法

第六步：段内排列计数

第七步：完整公式

第八步：高效计算

第九步：进一步优化

第十步：计算 $\sum_{i<j} \sum_{l \max(i,l)}$

第十一步：算法实现

算法复杂度

进一步优化

最终算法

算法复杂度

进一步优化到 $O(k)$

算法标签

总结

信息

1 条题解

「RMI 2018」W 题解

关键分析

1. W 形结构

2. 值的大小关系

3. 元素分配

解决方案

方法1：枚举转折点 + 组合计数

第一步：预处理频率

第二步：枚举转折点

第三步：优化枚举

第四步：计算固定转折点的排列数

第五步：生成函数方法

第六步：段内排列计数

第七步：完整公式

第八步：高效计算

第九步：进一步优化

第十步：计算 $\sum_{i<j} \sum_{l \max(i,l)}$

第十一步：算法实现

算法复杂度

进一步优化

最终算法

算法复杂度

进一步优化到 O(k)O(k)O(k)

算法标签

总结

「RMI 2018」W

信息

还没有账户？

登录

进一步优化到 $O(k)$