首页 > 搜索 > DFS搜索 > HDU 4025-Equation of XOR-DFS-[解题报告]HOJ
2015
04-15

HDU 4025-Equation of XOR-DFS-[解题报告]HOJ

Equation of XOR

问题描述 :

Recently, Jimmy is learning about linear algebra from Blue Mary while having the course of Boolean algebra in class offered by Prof. Z. Since Jimmy has been thoroughly bored by the boring homework assigned by two teachers, evil Jimmy plans to set a hard question to baffle them as revenge for their heavy tasks. As a result, Jimmy comes up with an idea that merging the knowledge from both the two classes and constructs a complicate problem: the XOR equation system.
Let’s consider the following equations:
(a11 . x1) ^ (a12 . x2) ^ … ^ (a1m . xm) = 0
(a21 . x1) ^ (a22 . x2) ^ … ^ (a2m . xm) = 0

(an1 . x1) ^ (an2 . x2) ^ … ^ (anm . xm) = 0
which satisfies the following conditions:
1.  aij in {0,1}   for 1 ≤ i ≤ n and 1 ≤ j ≤ m;
2.  xi in Si where Si is a subset of {0,1,2,3}, 1 ≤ i ≤ m;
3.  |Si| ≤ 3, 1 ≤ i ≤ m;
4.  1≤n ≤ 30, 1 ≤ m ≤ 22.

In the system of equations, operation “ . “ denotes the multiplication operation while “ ^ ” is for bitwise XOR. Moreover, the bitwise XOR takes two bit patterns of equal length and performs the logical XOR operation on each pair of corresponding bits. The result in each position is 1 if the two bits are different, and 0 if they are the same.
Rather than expecting a solution of a specified equation system, Jimmy would like to ask the teachers to calculate that how many distinct solutions can satisfy a given equation system. What a confusing puzzle! Help Jimmy’s teachers please!

输入:

There are several test cases. The first line of input is a single positive integer T (<= 15) indicating the number of test cases, then T cases follow.
For each test case, the first line contains two integers N and M giving the two dimensions of the equation system respectively where N is the number of rows and M for columns. Then N lines are following, each line contains m integers. Item at line i and column j represents aij. The next m lines are descriptions of Si that the leading integer K denotes the number of elements in Si and the following K integers represent elements.

输出:

There are several test cases. The first line of input is a single positive integer T (<= 15) indicating the number of test cases, then T cases follow.
For each test case, the first line contains two integers N and M giving the two dimensions of the equation system respectively where N is the number of rows and M for columns. Then N lines are following, each line contains m integers. Item at line i and column j represents aij. The next m lines are descriptions of Si that the leading integer K denotes the number of elements in Si and the following K integers represent elements.

样例输入:

1
1 2
1 1
3 0 1 2
2 3 1

样例输出:

1

拼死拼活就这一道题,写出来后发到博客装大牛,哈哈,其实还是个菜鸟。

http://acm.hdu.edu.cn/showproblem.php?pid=4025

计算值的压缩,因为每一个a和x不超过两个二进制位,最多有30个式子,供60位,所以可以用__int64存下所有的结果。枚举一半的x变量,保存结果,统计每个结果出现的次数,然后再枚举另一半x,二分查找是否有对应的解。

/*Equation of XOR*/
#include <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std;

struct Set{
    int k, num[5];
};
int ans_count, a1, a2, n, m;
int a[31][23];
Set s[23];
__int64 ans[(1<<22) + 2];
__int64 sum[(1<<22)+2];
__int64 final_ans;

int find(__int64 v)
{
    int left = 0, right = ans_count-1, mid;
    if (ans_count == 0) return -1;
    while (left < right-1) {
        mid = left + (right - left) / 2;
        if (v <= ans[mid]) right = mid;
        else  left = mid;
    }
    if (v == ans[left]) return left;
    if (v == ans[right]) return right;
    return -1;
}

void dfs_x1(int p, __int64 now)
{
    int i, j, x;
    __int64 tmp;
    if (p >= a2+1) {
        ans[ans_count++] = now;
        return;
    }
    for (i = 0; i < s[p].k; i++) {
        x = s[p].num[i];
        tmp = now;
        for (j = 1; j <= n; j++)   tmp ^= ((__int64)(a[j][p] * x)) << (2*(j-1));
        dfs_x1(p+1, tmp);
    }
}

void dfs_x2(int p, __int64 now)
{
    int i, j, x, ret;
    __int64 tmp;
    if (p >= a2+1) {
        ret = find(now);
        if (ret != -1) {
            final_ans += sum[ret];
        }
        return;
    }
    for (i = 0; i < s[p].k; i++) {
        x = s[p].num[i];
        tmp = now;
        for (j = 1; j <= n; j++)   tmp ^= ((__int64)(a[j][p] * x)) << (2*(j-1));
        dfs_x2(p+1, tmp);
    }
}

int main()
{
    int cs, tt, i, j, ss, n_count;

    scanf("%d", &tt);
    for (cs = 1; cs <= tt; cs++) {
        scanf("%d %d", &n, &m);
        for (i = 1; i <= n; i++) {
            for (j = 1; j <= m; j++) {
                scanf("%d", &a[i][j]);
            }
        }
        for (i = 1; i <= m; i++) {
            scanf("%d", &s[i].k);
            n_count = 0;
            ss = 0;
            for (j = 0; j < s[i].k; j++) {
                scanf("%d", &s[i].num[n_count]);
                if (ss & (1<<s[i].num[n_count])) continue;
                n_count++;
            }
            s[i].k = n_count;
        }

        ans_count = 0;
        a1 = 1;
        a2 = (m/2);
        dfs_x1(a1, 0LL);

        sort(ans, ans+ans_count);
//for (i = 0; i < ans_count; i++)  printf("%I64d  ", ans[i]); printf("\n");
        j = 0;
        sum[j] = 1;
        for (i = 1; i < ans_count; i++) {
            if (ans[j] == ans[i]) sum[j]++;
            else {
                ans[++j] = ans[i];
                sum[j] = 1;
            }
        }
        ans_count = j+1;
        final_ans = 0LL;
        a1 = a2 + 1;
        a2 = m;
        dfs_x2(a1, 0LL);

        printf("%I64d\n", final_ans);
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/moorage/article/details/6767057