usaco-2.2.2 集合

题目描述

给定正整数 $N$ ，把集合 $\{1,2,\dots,N\}$ 划分成两个子集，要求两个子集的数字和相等（交换两个集合算同一种方案），求划分方案总数，不存在则输出 $0$ 。例如 $N=7$ 时有 4 种，如 $\{1,6,7\}$ 与 $\{2,3,4,5\}$ 。输入一行一个整数 $N$ ；样例输入 7，样例输出 4。

思路

总和 $S=\frac{N(N+1)}{2}$ 为奇数时无解输出 0；否则用 0-1 背包计数求从 $1..N$ 中选数使和为 $S/2$ 的方案数： $dp[j]$ 表示和为 $j$ 的取法数，逐个加入数字 $i$ 并倒序转移 $dp[j] \leftarrow dp[j]+dp[j-i]$ 。每个无序划分在 $dp[S/2]$ 中被统计两次（选中的集合可以是两半中任意一个），最终答案为 $dp[S/2]/2$ 。

参考代码

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#!/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-04-18 10:00
# update_at: 2026-04-18 10:00

import sys


def count_subsets(n: int, target: int) -> int:
    """计算从 1 到 n 中选取若干互不相同的数使其和为 target 的方案数。"""
    dp = [0] * (target + 1)
    dp[0] = 1
    for num in range(1, n + 1):
        for s in range(target, num - 1, -1):
            dp[s] += dp[s - num]
    return dp[target]


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    try:
        n = next(data)
    except StopIteration:
        return
    total_sum = n * (n + 1) // 2

    # 和为奇数无法二等分；否则每个无序二划分对应含/不含某个元素的有序方案数的一半
    if total_sum % 2 != 0:
        print(0)
        return

    target = total_sum // 2
    ans = count_subsets(n, target) // 2
    print(ans)


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/**
 * 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-06 09:51
 * update_at: 2026-10-06 09:51
 */
#include <cstdio>

typedef long long ll;

const int MAXS = 800; // N 最大 39 时总和 N(N+1)/2 = 780，target 最大 390

ll n;
ll dp[MAXS]; // dp[j] 表示从 1..n 中选若干互不相同的数，和恰好为 j 的方案数

int main() {
    scanf("%lld", &n);

    ll sum = n * (n + 1) / 2; // 1..n 的总和

    // 总和为奇数时无法二等分，方案数为 0
    if (sum % 2 == 1) {
        printf("0\n");
        return 0;
    }

    ll target = sum / 2;

    // 0-1 背包计数：dp[0] = 1 表示空集这一种取法
    dp[0] = 1;
    for (ll i = 1; i <= n; i++) {
        // 倒序枚举容量，保证每个数字 i 只被选一次
        for (ll j = target; j >= i; j--) {
            dp[j] += dp[j - i];
        }
    }

    // 每个无序划分 {A, B} 在 dp 中被统计了两次（A 当选中集 / B 当选中集），除以 2
    printf("%lld\n", dp[target] / 2);
    return 0;
}

目录

题目描述

思路

参考代码