记$S(A)$为集合A中所有元素的和。

考虑集合$B=\{1,3,6,8,10,11\}$，B共有20个大小为3的子集，这些子集的元素和分别是： \begin{align*} S(\{1,3,6\})&=10, \\ S(\{1,3,8\})&=12, \\ S(\{1,3,10\})&=14, \\ S(\{1,3,11\})&=15, \\ S(\{1,6,8\})&=15, \\ S(\{1,6,10\})&=17, \\ S(\{1,6,11\})&=18, \\ S(\{1,8,10\})&=19, \\ S(\{1,8,11\})&=20, \\ S(\{1,10,11\})&=22, \\ S(\{3,6,8\})&=17, \\ S(\{3,6,10\})&=19, \\ S(\{3,6,11\})&=20, \\ S(\{3,8,10\})&=21, \\ S(\{3,8,11\})&=22, \\ S(\{3,10,11\})&=24, \\ S(\{6,8,10\})&=24, \\ S(\{6,8,11\})&=25, \\ S(\{6,10,11\})&=27, \\ S(\{8,10,11\})&=29. \end{align*} 其中有些和出现了不止一次，也有一些和是唯一的。

令$U(A,k)$为A的所有大小为$k$的子集的唯一元素和所组成的集合，例如在上例中，$U(B,3)=\{10,12,14,18,21,25,27,29\}$，因而$S(U(B,3))=156$。

现考虑有100个元素的集合$X=\{1^2, 2^2, \ldots, 100^2\}$，该集合有100891344545564193334812497256个大小为50的子集。

求$S(U(X,50))$。

本题难度:

解答

比较麻烦的多维动态规划问题。

用$f(i,j,k)$表示集合$\{1^2,\ldots,i^2\}$中大小为j且和为k的子集数量，并规定空集的大小与和均为$0$，即$f(0,0,0)=1$。

那么对有效的取值$i,j,k$而言就有 $$f(i,j,k)=f(i-1,j,k)+f(i-1,j-1,k-i^2).$$ 其中等式右侧的两项分别表示满足要求但不含$i^2$和满足要求且包含$i^2$的子集数量。

所谓有效的取值是指逻辑上有意义，例如显然j应该小于i，k不能小于0等等，无效取值一律赋0。

此外，子集数量可能很多，因此把大于等于2数一律赋作2。

最终结果是$115039000$。

m=295425
f=[[0]*(m+1) for j in range(51)]
f[0][0]=1
s=0
for i in range(101):
    s+=i*i
    for j in range(min(50,i),0,-1):
        for k in range(min(m,s),i*i-1,-1):
            f[j][k]=min(2,f[j][k]+f[j-1][k-i*i])
    print i
print sum(k for k in range(m+1) if f[50][k]==1)