题解：CF2134F-Permutation-Oddness

DimStar
  2026-03-04 11:02:27 2026-03-04 11:02:27 创建   2026-03-04 11:57:18 2026-03-04 11:57:18 更新      1.6k 字  7 分钟  

原题链接

前言

赛时只做了三道，本来只想改四道题，结果学长说后两道都可做，然后蒟蒻一眼见到这道题，只觉一脸懵，顶上的异或和 让我想到位运算，往后读题发现有组合数学，一看标签，啊呀，DP！我们没救了。

Solution

正如前言所述，这题看起来十分复杂 （不然也不会是F题） ，那么，从什么地方入手呢？
注意到，只有四个数字，那就看一下他们异或再 的结果都是什么。

0 1 2 3
0 0 1 2 1
1 1 0 1 2
2 2 1 0 1
3 1 2 1 0

发现了吗？相同的数结果是 。 和 ， 和 组合的结果是 。其余的组合结果是 。
那我们把任意一个可重排列中的 和 归为一组，染成红色， 和 染成蓝色，可以发现，现在排列变成了若干段红色段和蓝色段交替出现。接着，我们又有如下三个发现：

  • 红蓝色段的数量最多相差 。
  • 红蓝色段交替处有 的奇异度贡献。
  • 某种色段内只会有两种相邻数对，两数相同的贡献为 ，两数不同的贡献为 。

根据前两个性质，我们可以想到把两种色段分开处理，最后再合并计算答案。
以红色（ 和 ）为例，考虑如何处理？为了最后合并，我们要知道它被拆为了多少段，还要知道这么拆可能产生多少贡献，以及有几种得到这个贡献的方案，那么我们便设计出了DP状态及其含义： 表示将其拆为 段，贡献为 的方案数。
因此，要计算 就要枚举所有由 个 和 个 组成的字符串，再将其分割为若干个子串，最后统计。
对于一个02字符串来说，我们进一步将其分为由 或 构成的两种连续段，可以发现一组性质（注意与前面所述的“红蓝色段”的性质区分开来）：

  • 连续段的数量最多相差
  • 两种段交替处有 的奇异度贡献
  • 某种段内只会有相邻数对，没有贡献。

根据第一条性质，我们可以枚举由 构成的连续段的数量 ，可知由 构成的连续段的数量 。那么，使用插板法可得这样的02字符串的数量为（最后一个乘数表示将相差的那一段选择放在哪一侧）：

设有 个连续段，显然有 个不同的相邻对，因为总长度为 ，有 个相邻对，所以有 个相同相邻对。接下来，为了将字符串分割为若干个子串，我们可以枚举在两种相邻对中各要“切几刀”，设 分别为在不同的相邻对及相同的相邻对中的分割次数，枚举 就可以得到若干种分割方式。它会将字符串分割为 段，贡献为 ，那就可以得到该方式对 的答案贡献为（前两个乘数需要先预计算）：

通过同样的方式计算蓝色段（ 和 ），最后将两组结果合并（具体详见代码），即可得到最终答案。

时间复杂度分析

设 。
预先计算 复杂度为 。
DP部分枚举 复杂度 。
最后合并统计答案枚举总段数 和两种颜色贡献 ，复杂度 。
总体时间复杂度 ，本题 ，在 时限下可以通过。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
const LL mod = 1e9 + 7;
LL dp[2][805][805]; // dp[0] for 0,2; dp[1] for 1,3 表示i个段，贡献为j的方案数
LL g[2][805];       // g[0] for 0,2; g[1] for 1,3 表示有i个连续段的方案数
LL c[4], n;
LL ans[1605];
LL inv[805], fac[805], facinv[805];
void init() // 因为有模和组合数计算，所以预处理阶乘及其逆元
{
    fac[0] = fac[1] = 1;
    inv[0] = inv[1] = 1;
    facinv[0] = facinv[1] = 1;
    for (int i = 2; i <= 800; i++)
    {
        fac[i] = ((fac[i - 1] % mod) * (i % mod)) % mod;
        inv[i] = ((inv[mod % i] % mod) * ((mod - mod / i) % mod)) % mod;
        facinv[i] = ((facinv[i - 1] % mod) * (inv[i] % mod)) % mod;
    }
}
void clear() // 多测清空
{
    memset(dp, 0, sizeof(dp));
    memset(g, 0, sizeof(g));
    memset(ans, 0, sizeof(ans));
}
LL C(LL n, LL m)
{
    if (m > n || m < 0)
        return 0;
    return (((fac[n] * facinv[m]) % mod) * facinv[n - m]) % mod;
}
void solve()
{
    clear();
    cin >> c[0] >> c[1] >> c[2] >> c[3];
    n = (c[0] + c[1] + c[2] + c[3]) % mod;

    // calc g
    for (int l1 = 1; l1 <= c[0]; l1++)
    {
        for (int j = -1; j <= 1; j++)
        {
            int l2 = l1 + j;
            if (l2 > 0 && l2 <= c[2])
            {
                g[0][l1 + l2] = (g[0][l1 + l2] + (((C(c[0] - 1, l1 - 1) % mod) * (C(c[2] - 1, l2 - 1) % mod)) % mod * (C(2, j + 1) % mod)) % mod) % mod;
            }
        }
    }
    for (int l3 = 1; l3 <= c[1]; l3++)
    {
        for (int j = -1; j <= 1; j++)
        {
            int l4 = l3 + j;
            if (l4 > 0 && l4 <= c[3])
            {
                g[1][l3 + l4] = (g[1][l3 + l4] + (((C(c[1] - 1, l3 - 1) % mod) * (C(c[3] - 1, l4 - 1) % mod)) % mod * (C(2, j + 1) % mod)) % mod) % mod;
            }
        }
    }

    // dp
    for (int l = 1; l <= c[0] + c[2]; l++)
    {
        if (!g[0][l]) // 随便的优化
            continue;
        for (int k1 = 0; k1 <= l - 1; k1++)
        {
            for (int k2 = 0; k2 <= c[0] + c[2] - l; k2++)
            {
                dp[0][k1 + k2 + 1][(l - 1) - k1] = (dp[0][k1 + k2 + 1][(l - 1) - k1] + ((((g[0][l] % mod) * (C(l - 1, k1) % mod)) % mod) * (C(c[0] + c[2] - l, k2) % mod)) % mod) % mod;
            }
        }
    }
    for (int l = 1; l <= c[1] + c[3]; l++)
    {
        if (!g[1][l])
            continue;
        for (int k1 = 0; k1 <= l - 1; k1++)
        {
            for (int k2 = 0; k2 <= c[1] + c[3] - l; k2++)
            {
                dp[1][k1 + k2 + 1][(l - 1) - k1] = (dp[1][k1 + k2 + 1][(l - 1) - k1] + ((((g[1][l] % mod) * (C(l - 1, k1) % mod)) % mod) * (C(c[1] + c[3] - l, k2) % mod)) % mod) % mod;
            }
        }
    }

    // 合并
    for (int k = 1; k <= max(c[0] + c[2], c[1] + c[3]); k++) // 枚举段数
    {
        for (int i = 0; i <= c[0] + c[2]; i++) // 枚举红色贡献
        {
            for (int j = 0; j <= c[1] + c[3]; j++) // 枚举蓝色贡献
            {
                // 两种各k段
                ans[(i + j) * 2 + k * 2 - 1] = (ans[(i + j) * 2 + k * 2 - 1] + (((((dp[0][k][i] % mod) * (dp[1][k][j] % mod)) % mod) * 2) % mod)) % mod;
                // 一种k段,另一种k+1段
                ans[(i + j) * 2 + k * 2] = (ans[(i + j) * 2 + k * 2] + (((((dp[0][k][i] % mod) * (dp[1][k + 1][j] % mod)) % mod) + (((dp[0][k + 1][i] % mod) * (dp[1][k][j] % mod)) % mod)) % mod)) % mod;
            }
        }
    }
    for (int i = 0; i <= (2 * (n - 1)); i++)
    {
        cout << ans[i] % mod << " ";
    }
    cout << endl;
    return;
}
int main()
{
    init();
    int T;
    cin >> T;
    while (T--)
        solve();
    return 0;
}
  • 标题: 题解：CF2134F-Permutation-Oddness
  • 作者: DimStar
  • 创建于 : 2026-03-04 11:02:27
  • 更新于 : 2026-03-04 11:57:18
  • 链接: https://dimstar-zhang.github.io/2026/03/04/题解：CF2134F-Permutation-Oddness/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
目录
题解：CF2134F-Permutation-Oddness
  1. 前言
  2. Solution
  3. 时间复杂度分析
  4. Code