编程之美_集合

描述

统计满足下列条件的集合对(A, B)的数量：

• A,B都是{1, 2, …, N}的子集；

• A,B没有公共的元素；

• f(A)<= f(B)。f(S)定义为S中所有元素的按位异或和。例如， f({}) = 0, f({1, 3}) = 2。

因为答案可能很大，你只需要求出它除以M的余数。

输入

第一行一个整数T (1 ≤ T ≤ 10)，表示数据组数。

接下来是T组输入数据，测试数据之间没有空行。

每组数据格式如下：

仅一行，2个整数N和M (1 ≤ M ≤ 108)。

输出

对每组数据，先输出“Case x: ”，然后接一个整数，表示所求的结果。

数据范围

小数据：1 ≤ N ≤ 20

大数据：1 ≤ N < 212

样例输入

1
3 100000000

样例输出

Case 1: 18

• 分析：
  思考一下问题的本质，对于两个不相交的集合A和B，如果f值不相等那么答案为1，如果相等那么答案为2。对于所有的A和B的情况（设为P），设A和B相等的情况（设为x），那么结果就等于（P + x）/ 2。计算两个数的值相等可以用异或为零，那么就可以用dp来解决了dp【n】【异或值】
• 重点：
  这个题目答案是需要对m取模的，而答案的计算中包括了一个除法，所以需要额外处理。在计算中，对于p和x肯定是取过模的，否则计算不出来。但是这个题有点特殊，最后结果是除以2，也就是右移一位，也就是说如果我们一直对2*m取模的话，最后右移一位（除以2）结果就对了。
  延伸一下，对于只含有对2^n做除法的式子且最终结果对m取模，我们可以通过对m * 2^n取模，最后直接除以2^n即可
• 总结：
  对于判断两个数相等，可以采用异或值为零来解决。
  

const int MAXN = 1100;
const double PI = acos(-1.0);

int dp[MAXN];

int main()
{
//    freopen("in.txt", "r", stdin);
    int n;
    while (cin >> n)
    {
        CLR(dp, 0);
        int all = (1 << n) - 1;
        for (int i = 1, cnt = 1; cnt <= n; cnt++, i <<= 1)
        {
            FED(j, all, 0)
            {
                if (j & i)
                {
                    dp[j] = dp[i ^ j] ^ cnt;
                }
            }
        }
        int ans = 0;
        FE(i, 0, all) FE(j, 0, all)
        {
            if (!(i & j) && dp[i] >= dp[j]) ans++;
        }
        WI(ans);
    }
    return 0;
}

const int MAXN = 1100;
const double PI = acos(-1.0);

LL dp[2][MAXN];

LL my(int n)
{
    LL ret = 1;
    for (int i = 0; i < n; i++) ret *= 3;
    return ret;
}

int main()
{
//    freopen("in.txt", "r", stdin);
    int n;
    while (cin >> n)
    {
        int cur = 0, all;
        CLR(dp, 0); dp[cur][0] = 1;
        for (all = 1; all <= n; all <<= 1);
        all -= 1;
        for (int cnt = 1; cnt <= n; cnt++)
        {
            cur ^= 1;
            CLR(dp[cur], 0);
            FE(j, 0, all)
            {
                dp[cur][j] += dp[cur ^ 1][j];
                dp[cur][j ^ cnt] += dp[cur ^ 1][j] * 2;
            }
        }
        cout << (my(n) + dp[cur][0]) / 2 << endl;
    }
    return 0;
}