HDU-5119: Happy Matt Friends

DP 高斯消元

Problem Description

Matt has N friends. They are playing a game together.

Each of Matt’s friends has a magic number. In the game, Matt selects some (could be zero) of his friends. If the xor (exclusive-or) sum of the selected friends’magic numbers is no less than M , Matt wins.

Matt wants to know the number of ways to win.

Input

The first line contains only one integer T , which indicates the number of test cases.

For each test case, the first line contains two integers $N, M (1 ≤ N ≤ 40, 0 ≤ M ≤ 10^6)$.

In the second line, there are N integers $ki (0 ≤ ki ≤ 10^6)$, indicating the i-th friend’s magic number.

Output

For each test case, output a single line “Case #x: y”, where x is the case number (starting from 1) and y indicates the number of ways where Matt can win.

Sample Input

2
3 2
1 2 3
3 3
1 2 3

Sample Output

Case #1: 4
Case #2: 2

Hint

In the first sample, Matt can win by selecting:
friend with number 1 and friend with number 2. The xor sum is 3.
friend with number 1 and friend with number 3. The xor sum is 2.
friend with number 2. The xor sum is 2.
friend with number 3. The xor sum is 3. Hence, the answer is 4.

题意： t组数据，每组输入一个n和m，然后输入n个数，要从这n个数中随便选一些出来，让他们的异或值大于等于m，求方案数量。

分析：由于时间和内存都开得比较大，可以考虑直接暴力求解。也可以用高斯消元。

DP : dp[i][j]表示前i个数异或起来的值为j的方案数是多少，那么就可以得到dp[i][j]=dp[i-1][j]+dp[i-1][j^a[i]]，前i-1个数异或等于j的个数加上前i-1个数异或起来为j^a[i]的个数。因为j^a[i]^a[i]=j。
可以用滚动数组优化，由于dp只与其前一个状态有关系，因此得到dp[i][j]=dp[i^1][j]+dp[i^1][j^a[i]]。

• 代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1 << 20;
int a[50];
LL dp[2][maxn];
//int dp[50][maxn];
int main()
{
    int t, o = 0;
    scanf("%d", &t);
    while(t--)
    {
        int n, m;
        scanf("%d%d", &n, &m);
        for(int i = 1; i <= n; i++)
            scanf("%d", &a[i]);
        memset(dp, 0, sizeof(dp));
        dp[0][0] = 1;
        int cur = 1;
        for(int i = 1; i <= n; i++)
        {
            for(int j = 0; j < maxn; j++)
            {
                //dp[i][j]=dp[i-1][j]+dp[i-1][j^a[i]];
                dp[cur][j] = dp[cur ^ 1][j] + dp[cur ^ 1][j ^ a[i]];
            }
            cur ^= 1;
        }
        LL ans = 0;
        printf("Case #%d: ", ++o);
        for(int i = m; i < maxn; i++)
            ans += dp[cur ^ 1][i];
        printf("%lld\n", ans);
    }
    return 0;
}

高斯消元： 求出小于m的个数，用总数减去它即可。具体做法：首先把每个数拆成二进制存在二维数组里，每个数存一列，从上到下为高位到低位，m放在最后一列。一行一行处理，如果某行m的二进制为1，那么将它变为0，处理这一行及其以上的矩阵，$ans-=2^{res}$，ans为总方案数。
每次都要重新构造矩阵。

• 代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int mp[55][55];
int tp[55][55];
int gauss(int A[][55], int n, int m)
{
    int r = 0;
    for(int i = 0; i < m && r < min(n, m); i++)
    {
        for(int j = r; j < n; j++)
            if(A[j][i])
            {
                for(int k = i; k < m; k++)
                    swap(A[j][k], A[r][k]);
                break;
            }
        if(A[r][i] == 0) continue;
        for(int j = 0; j < n; j++)
        {
            if(j != r && A[j][i])
                for(int k = i; k < m; k++)
                    A[j][k] ^= A[r][k];
        }
        r++;
    }
    if(r == 0) return 0;
    for(int i = 0; i < m - 1; i++)
        if(A[r - 1][i] != 0)
            return r;
    return -1;
}
int main()
{
    int t,o=0;
    scanf("%d", &t);
    while(t--)
    {
        int n, m, x;
        memset(tp, 0, sizeof(tp));
        scanf("%d%d", &n, &m);
        for(int i = 0; i < m; i++)
        {
            int k;
            scanf("%d",&k);
            while(k--)
            {
                scanf("%d", &x);
                tp[x - 1][i] = 1;
            }
        }
        int q;
        scanf("%d", &q);
        printf("Case %d:\n",++o);
        while(q--)
        {
            memcpy(mp, tp, sizeof(tp));
            for(int i = 0; i < n; i++)
            {
                scanf("%d", &x);
                mp[i][m] = x;
            }
            int cnt=gauss(mp,n,m+1);
            LL ans=1LL<<(m-cnt);
            if(cnt==-1)
                ans=0;
            printf("%lld\n",ans);
        }
    }
    return 0;
}