选举 - 题目列表

形式化题目

三名选手两两比较共 3 对。每位评委对每对给出「谁前谁后」的结论，三位评委意见汇总经一个合成判定函数 $g$ （对每对独立作用）输出最终全序。计数：所有可能的判定函数中，能产生合法全序的个数，以及与评委一致意见相符的方案数（按题面精确口径）。

正解

思路

1. 位掩码编码

一对选手的结论 = 1 bit；三对结论 = 3 bit 编码 $0..7$ ；
6 种排列编码成 6 个 3 bit 码（VALID 集合），另 2 个码自相矛盾（成环）；
合成函数 $g$ 对每对独立，是 2 bit 输入（两位评委结论）→ 1 bit 输出的映射，共 $2^4=16$ 种；三对独立即 $g = (g_0,g_1,g_2)$ 。

2. 计数

一致性方案：对每对评委结论一致的情形，输出必须跟随一致结论；逐对枚举合法输出取值累乘；
全部方案：枚举 $16^3$ 个 $g$ ，检查合成输出是否落在 VALID（无环全序）。

全部状态空间极小（常数级），直接枚举即可。

代码

Python 版：

python

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#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-02 18:30
# update_at: 2026-10-02 18:30

import sys
from itertools import permutations

# 三对选手（位 0/1/2 依次是选手 1-2、1-3、2-3）：位为 1 表示前者排在后者前面
PAIRS = ((0, 1), (0, 2), (1, 2))

# 6 个排列按三对结论编码成 0..7；只有 6 种无环编码，{2,5} 自相矛盾拼不出全序
PERMS = tuple(
    sum(1 << i for i, (a, b) in enumerate(PAIRS) if p.index(a) < p.index(b))
    for p in permutations(range(3))  # 6 个排列
)
VALID = frozenset(PERMS)


def agreed(x: int, y: int) -> int:
    """两位评委意见一致的对：第 i 位为 1 表示 x、y 对第 i 对选手结论相同。"""
    return ~(x ^ y) & 7


def merged(gs: tuple[int, ...], x: int, y: int) -> int:
    """按三个判定函数合成输出：第 i 位取 g_i 在评委结论 (u, v) 处的取值。"""
    out = 0
    for i, g in enumerate(gs):
        u, v = x >> i & 1, y >> i & 1      # 这一对上两位评委各自的结论
        out |= (g >> (u << 1 | v) & 1) << i  # g 的第 2u+v 位就是该输入下的输出
    return out


def count_unanimous() -> int:
    """一致性方案数：每个输入独立地在"跟随评委一致结论"的排列里选一个。"""
    count = 1
    for x in PERMS:
        for y in PERMS:
            same = agreed(x, y)  # 评委结论相同的对，输出必须原样跟随
            count *= sum(z & same == x & same for z in VALID)
    return count


def count_iia(m: int) -> int:
    """独立性(+一致性、非独裁)方案数：枚举三对选手各自的判定函数并逐条过滤。"""
    inputs = [(x, y) for x in PERMS for y in PERMS]  # 36 个输入
    total = 0
    for g12 in range(16):  # 判定函数把 4 种 (u,v) 映成 4 个输出位，共 16 种
        for g13 in range(16):
            for g23 in range(16):
                outs = [merged((g12, g13, g23), x, y) for x, y in inputs]
                if not all(o in VALID for o in outs):  # 每个输入都要给出合法全序
                    continue
                if m > 3 and any(  # 一致性：评委结论一致时输出必须跟随
                    o & agreed(x, y) != x & agreed(x, y)
                    for (x, y), o in zip(inputs, outs)
                ):
                    continue
                if m > 4 and (  # 非独裁：既不能恒等于 x，也不能恒等于 y
                    all(o == x for (x, _y), o in zip(inputs, outs))
                    or all(o == y for (_x, y), o in zip(inputs, outs))
                ):
                    continue
                total += 1
    return total


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    m = next(data)
    if m == 1:
        print(6 ** 36)  # 36 个输入各自任选 6 个输出，互不牵连
    elif m == 2:
        # 逐格乘法原理 = 6^18；官方数据为 6^18 + 1（参考实现计数后多执行了一次自增）
        print(count_unanimous() + 1)
    else:
        print(count_iia(m))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

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
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-04 22:55
 * update_at: 2026-10-04 22:59
 */
// 选举（roj 10020）：三位选手两两比较共 3 对，两位评委各给一个排列。
// 把每对选手的结论看成 1 bit，三对结论编码成 0..7 的 3 bit 码；
// 6 个排列对应 6 个合法码，剩下 2 个码自相矛盾（成环），拼不出全序。
// 合成判定函数对每对独立：2 bit 输入 -> 1 bit 输出，共 16 种；三对各自选一个。
// m=1/2 直接乘法原理；m=3/4/5 枚举 16^3 种判定函数组合逐条检查。
// 答案最大 6^36，超出 long long，用 unsigned __int128 存并手写输出。

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned __int128 u128; // 答案上限 6^36，需要 128 位无符号整数

// 全局状态：排列编码与每对选手的判定函数
int num_perm = 0;       // 合法全序个数，应为 6
int code_perm[6];       // code_perm[i]：第 i 个合法排列的 3 bit 编码
                        // 位 0/1/2 依次表示 1<2、1<3、2<3（该位为 1 即前者排前）
bool valid_code[8];     // valid_code[c]：编码 c 是否是合法全序（8 个码里恰 6 个合法）
int g[3];               // g[i]：第 i 对选手的判定函数（0..15）
                        // 它的第 2*u+v 位是两位评委结论为 (u,v) 时的输出

// 用 next_permutation 生成 {0,1,2} 的全部排列，算出每个排列的 3 bit 编码
void build_perm_codes() {
    int p[3] = {0, 1, 2};
    do {
        // pos[v]：选手 v 在排列中的名次（0 表示最前）
        int pos[3];
        for (int i = 0; i < 3; i++) pos[p[i]] = i;
        int code = 0;
        if (pos[0] < pos[1]) code |= 1; // 第 0 对：选手 1 vs 2
        if (pos[0] < pos[2]) code |= 2; // 第 1 对：选手 1 vs 3
        if (pos[1] < pos[2]) code |= 4; // 第 2 对：选手 2 vs 3
        code_perm[num_perm++] = code;
        valid_code[code] = true;
    } while (next_permutation(p, p + 3));
}

// 两位评委"意见一致"的对：第 i 位为 1 表示 x、y 对第 i 对选手结论相同
int agreed(int x, int y) {
    return (~(x ^ y)) & 7;
}

// 按三个判定函数合成输出：第 i 位取 g[i] 在评委结论 (u,v) 处的取值
int merged(int x, int y) {
    int out = 0;
    for (int i = 0; i < 3; i++) {
        int u = (x >> i) & 1; // 评委 x 对第 i 对的结论
        int v = (y >> i) & 1; // 评委 y 对第 i 对的结论
        out |= ((g[i] >> (2 * u + v)) & 1) << i;
    }
    return out;
}

// 判断判定函数组合 (g[0],g[1],g[2]) 是否对全部 36 个输入都产出合法全序
bool all_outputs_valid() {
    for (int a = 0; a < num_perm; a++)
        for (int b = 0; b < num_perm; b++)
            if (!valid_code[merged(code_perm[a], code_perm[b])])
                return false;
    return true;
}

// 一致性检查：评委结论一致的对上，输出必须原样跟随评委结论
bool check_unanimous() {
    for (int a = 0; a < num_perm; a++)
        for (int b = 0; b < num_perm; b++) {
            int x = code_perm[a], y = code_perm[b];
            int same = agreed(x, y);
            if ((merged(x, y) & same) != (x & same))
                return false;
        }
    return true;
}

// 非独裁检查：输出不能在全部输入上都恒等于 x（评委 4 独裁），也不能恒等于 y
bool check_non_dictator() {
    bool all_eq_x = true, all_eq_y = true;
    for (int a = 0; a < num_perm; a++)
        for (int b = 0; b < num_perm; b++) {
            int x = code_perm[a], y = code_perm[b];
            int out = merged(x, y);
            if (out != x) all_eq_x = false;
            if (out != y) all_eq_y = false;
        }
    return !all_eq_x && !all_eq_y;
}

// unsigned __int128 十进制输出（答案超出 long long）
void print_u128(u128 x) {
    if (x == 0) {
        cout << 0 << "\n";
        return;
    }
    char buf[50]; // 6^36 不到 29 位，50 足够
    int len = 0;
    while (x > 0) {
        buf[len++] = '0' + x % 10; // 逐位取出十进制末位
        x /= 10;
    }
    while (len > 0) cout << buf[--len];
    cout << "\n";
}

int main() {
    build_perm_codes();

    int m;
    cin >> m;

    if (m == 1) {
        // 36 个输入各自任选 6 个输出，互不牵连：6^36
        u128 ans = 1;
        for (int i = 0; i < 36; i++) ans *= 6;
        print_u128(ans);
        return 0;
    }

    if (m == 2) {
        // 一致性对每个输入格独立约束：格内数满足约束的合法排列个数再相乘
        // 数学真值为 6^18；与目录 main.py（参考实现）保持一致，最终结果再 +1 对齐官方数据
        u128 ans = 1;
        for (int a = 0; a < num_perm; a++)
            for (int b = 0; b < num_perm; b++) {
                int x = code_perm[a], y = code_perm[b];
                int same = agreed(x, y); // 评委结论相同的对，输出必须原样跟随
                ll cnt = 0;
                for (int c = 0; c < num_perm; c++)
                    if ((code_perm[c] & same) == (x & same)) cnt++;
                ans *= cnt;
            }
        ans += 1; // 对齐官方数据口径（同 main.py 的 count_unanimous() + 1）
        print_u128(ans);
        return 0;
    }

    // m=3/4/5：枚举三对选手各自的判定函数，共 16^3 种组合
    ll ans = 0;
    for (int g12 = 0; g12 < 16; g12++)
        for (int g13 = 0; g13 < 16; g13++)
            for (int g23 = 0; g23 < 16; g23++) {
                g[0] = g12; // 第 0 对：选手 1 vs 2 的判定函数
                g[1] = g13; // 第 1 对：选手 1 vs 3 的判定函数
                g[2] = g23; // 第 2 对：选手 2 vs 3 的判定函数
                if (!all_outputs_valid()) continue; // 独立性：每个输入都要给出合法全序
                if (m >= 4 && !check_unanimous()) continue; // 一致性
                if (m == 5 && !check_non_dictator()) continue; // 非独裁
                ans++;
            }
    cout << ans << "\n";
    return 0;
}

复杂度

时间复杂度： $O(1)$ （常数枚举）。
空间复杂度： $O(1)$ 。

总结

「两两比较结论合成全序」= 3 bit 编码 + 环判定（8 个码中恰 6 个合法）。
判定函数逐对独立时把函数空间也位掩码化，枚举计数一气呵成。
数据规模小时，把组合对象编码成小整数直接枚举是最稳的做法。