hdu 4025 Equation of XOR 状态压缩

思路：

设: 方程为

1*x1 ^ 1*x2 ^ 0*x3 = 0;

0*x1 ^ 1*x2 ^ 1*x3 = 0;

1*x1 ^ 0*x2 ^ 0*x3 = 0

把每一列压缩成一个64位整数，因为x范围为 (0 1 2 3) 二进制位不超过2, 方程组行数不超过30 则用一个大于60位整数就能表示每一列的状态,然后枚举各列就可以了。

如上面方程组

第一列为 1 0 1 ，可写为a1 = 11 00 11, 假设x1取2, 则第一列 s1 = 10 10 10, s1&a1 = 10 00 10 即为第一列的状态

第二列 a2 = 11 11 00 设x2 = 1 则 s2 = 01 01 01, 第二列状态为 a2&s2 = 01 01 00

第三列 a3 = 00 11 00 设x3 = 3 则 s3 = 11 11 11, 第三列状态为 a3&s3 = 00 11 00

对每列状态异或 (a1&s1) ^ (a2&s2) ^ (a3&s3) = 11 10 10 显然 x1=2 x2=1 x3=3 不是方程组的解

代码如下：

 #include<cstdio>

 #include<map>

 #include<cstring>

 #define ll __int64

 using namespace std;

 ll a[],x[][],ans;

 map<ll,ll>p;

 void dfs(int d,int n,ll res,ll f)

 {

     if(d==n){

         if(f) p[res]++;

         else if(p[res]) ans+=p[res];

         return ;

     }

     for(int i=;i<=x[d][];i++){

         ll temp=x[d][i]&a[d];

         dfs(d+,n,temp^res,f);

     }

 }

 int main()

 {

     int t,i,j,n,m,k;

     ll temp=,te;

     scanf("%d",&t);

     while(t--){

         scanf("%d%d",&n,&m);

         memset(a,,sizeof(a));

         memset(x,,sizeof(x));

         p.clear();

         for(i=;i<n;i++)

         for(j=;j<m;j++){

             scanf("%I64d",&te);

             if(te)

                 a[j]|=(temp<<(*i));

         }

         for(i=;i<m;i++){

             scanf("%d",&x[i][]);

             for(j=;j<=x[i][];j++){

                 scanf("%I64d",&te);

                 x[i][j]=te;

                 for(k=;k<n;k++){

                     x[i][j]|=(te<<(*k));

                 }

             }

         }

         ans=;

         dfs(,m/,,);

         dfs(m/,m,,);

         printf("%I64d\n",ans);

     }

     return ;

 }

巴特西

hdu 4025 Equation of XOR 状态压缩

最新文章

热门文章