首页 > 代码库 > 编程之美_集合

编程之美_集合

时间限制:12000ms
单点时限:6000ms
内存限制:256MB

描写叙述

统计满足下列条件的集合对(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就可以

  • 总结:
    对于推断两个数相等。能够採用异或值为零来解决。
代码是赛后自己写的,没有依照题目要求,懂什么意思即可,(小数据,未取模)
忽略之吧..... 才发现这个对于n=20的数据规模是不行的
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;
}



编程之美_集合