Project Euler 201

发表于 2022-05-30 更新于 2023-07-03 分类于 Project Euler 阅读次数： 61 本文字数： 2.1k 阅读时长 ≈ 2 分钟

Project Euler 201

题目

Subsets with a unique sum

For any set $A$ of numbers, let $sum (A)$ be the sum of the elements of $A$ .

Consider the set $B = {1, 3, 6, 8, 10, 11}$ .

There are $20$ subsets of $B$ containing three elements, and their sums are:

$sum ({1, 3, 6}) = 10$ ,
$sum ({1, 3, 8}) = 12$ ,
$sum ({1, 3, 10}) = 14$ ,
$sum ({1, 3, 11}) = 15$ ,
$sum ({1, 6, 8}) = 15$ ,
$sum ({1, 6, 10}) = 17$ ,
$sum ({1, 6, 11}) = 18$ ,
$sum ({1, 8, 10}) = 19$ ,
$sum ({1, 8, 11}) = 20$ ,
$sum ({1, 10, 11}) = 22$ ,
$sum ({3, 6, 8}) = 17$ ,
$sum ({3, 6, 10}) = 19$ ,
$sum ({3, 6, 11}) = 20$ ,
$sum ({3, 8, 10}) = 21$ ,
$sum ({3, 8, 11}) = 22$ ,
$sum ({3, 10, 11}) = 24$ ,
$sum ({6, 8, 10}) = 24$ ,
$sum ({6, 8, 11}) = 25$ ,
$sum ({6, 10, 11}) = 27$ ,
$sum ({8, 10, 11}) = 29$ .

Some of these sums occur more than once, others are unique.

For a set $A$ , let $U (A, k)$ be the set of unique sums of $k$ -element subsets of $A$ , in our example we find $U (B, 3) = {10, 12, 14, 18, 21, 25, 27, 29}$ and $sum (U (B, 3)) = 156$ .

Now consider the $100$ -element set $S = {1^{2}, 2^{2}, \dots, 100^{2}}$ .

$S$ has $100891344545564193334812497256$ $50$ -element subsets.

Determine the sum of all integers which are the sum of exactly one of the $50$ -element subsets of $S$ , i.e. find $sum (U (S, 50))$ .

解决方案

使用动态规划的思想解决集合的计数问题。

令 $M = 100, N = 50, S$ 为 $M^{2}$ 以内的最大的 $N$ 个平方数之和。

那么，设状态 $f (i, j, k) (0 \leq i \leq M, 0 \leq j \leq min (i, M), 0 \leq k \leq S)$ 表示集合 ${1^{2}, 2^{2}, \dots, i^{2}}$ 中，有多少个子集满足以下两个条件：

子集的大小为 $j$
子集的元素和为 $k$

其中，空集 $\emptyset$ 没有使用任何元素，因此大小为 $0$ ，元素和为 $0$ ，作为初始状态出现。

可以列出关于 $f (i, j, k)$ 的状态转移方程：

$f (i, j, k) = {\begin{aligned} 1 & if i = 0 \land j = 0 \land k = 0 \\ 0 & else if i = 0 \\ f (i - 1, j, k) & else if j < i^{2} \\ f (i - 1, j, k) + f (i - 1, j - 1, k - i^{2}) & else \end{aligned}$

对于方程最后一行，新数 $i^{2}$ 要么被使用了，就 $f (i - 1, j - 1, k - i^{2})$ 中的所有集合都添加一个 $i^{2}$ ；要么没有被使用，直接将旧状态 $f (i - 1, j, k)$ 记录。

因此，最终答案为 $\sum_{k = 1}^{S} k \cdot [f (M, N, k) = 1]$ 。其中， $[]$ 表示示性函数，表示 $[]$ 里面的值是否为真，如果为真，那么值为 $1$ ，否则值为 $0$ .

由于本题只关心 $f$ 的值是否为 $0, 1$ ，或者是超过 $2$ ，因此为 $f$ 定义一个新运算 $\circ$ ： ${0, 1, 2}^{2} \to {0, 1, 2}$ ，其中 $a \circ b = min (a + b, 2)$ 。因此不需要计算 $f$ 的真实值，避免了溢出问题。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int M=100,N=50;
const int S=M*(M+1)*(2*M+1)/6-N*(N+1)*(2*N+1)/6;
int f[N+1][S+1];
int add[3][3];
int main() {
    f[0][0] = 1;
    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++)
            add[i][j] = min(2, i + j);
    for (int i = 1, sum = 0; i <= M; i++) {
        int v = i * i;
        sum += v;
        for (int j = min(N, i); j >= 1; j--)
            for (int k = min(S, sum); k >= v; k--)
                f[j][k] = add[f[j][k]][f[j - 1][k - v]];
    }
    ll ans = 0;
    for (int i = 1; i <= S; i++)
        if (f[N][i] == 1) ans += i;
    printf("%lld\n", ans);
}