Problem Description
题目来源：http://blog.csdn.net/ljhandlwt/article/details/75014415 给定n，给定池，求池的子集的和为n的个数。池为2^0,2^0,2^1,2^1…包含任意2的次幂，且每个数都有两份。
Solution
对于任意2^i,有2^i=2^i=2^(i-1)*2=sum(2^(i-j))+2^(i-j-1)*2
其形式为连续的2^次幂累加及末尾最低项乘2。
题目表示任意2的次幂有两份。
因此若n=2^N+2^M,且N<M,
则我们可以认为，2^M只能来自于2^N,2^N+1,.....2^M。
（更低位中一定存在一位已被2^N使用了两次。特殊的，若2^N只使用了自己，2^M可以使用更低位，但其方案与2^N使用更低位是重复的）
将n按二进制分解，有n=2^a1+2^a2+....2^am, a1<a2<...<am
则可以dp，f[i]表示凑到2^ai时的方案数。
对于凑2^a[i]，方案总共a[i]-a[i-1]+1种。
这里的一个问题是2^a[i-1]可能在f[i-1]用到过，所以需要容斥一下。
2^a[i-1]是凑2^a[i-1]的方案一种，其对于f[i-1]的总贡献就是f[i-2]。
此时，对于f[i]，占用2^a[i-1]的那一种方案不可用，其他可用。
同理，f[i-1]的剩余部分可以使用f[i]的所有方案。
所以有：
f[i]=(f[i-1]-f[i-2])*(a[i]-a[i-1]+1)+f[i-2]*(a[i]-a[i-1])
即
f[i]=f[i-1]*(a[i]-a[i-1]+1)-f[i-2]
PS：对于本题，用f[i][0/1]表示凑到第i个数时，用或者不用自己来凑，这样的DP方式可能更自然。因为笔者智商极低，使用这种二维DP做完后才发现可以化简成一维，而后强行思考，才得出了这种容斥思路。
Code
#include <cstdio>
using namespace std;
int a[
66],n,f[
66];
int main()
{
int N;
while (
scanf(
"%d",&N)!=EOF)
{
int i=
0; n=
0;
while (N)
{
if (N%
2) a[++n]=i;
N/=
2; i++;
}
f[
0]=
1; f[
1]=a[
1]+
1;
for (i=
2;i<=n;i++) f[i]=f[i-
1]*(a[i]-a[i-
1]+
1)-f[i-
2];
printf(
"%d\n",f[n]);
}
}
