[Gauss]HDOJ3364 Lanterns

题意：有n个灯笼，m个开关

每个开关可以控制k个灯笼, 然后分别列出控制的灯笼的编号(灯笼编号为1到n)

下面有Q个询问，每个询问会有一个最终状态(n个灯笼为一个状态)0代表关 1代表开

问到达这种状态，按开关的方法总数

解释一下案例：

3 2 (有3个灯笼， 2个开关)

2 1 2 (第一个开关控制2个灯笼，这两个灯笼的编号是1、2)

2 1 3 (第一个开关控制2个灯笼，这两个灯笼的编号是1、3)

2 (2个询问)

0 1 1 (这3个灯笼变为关、开、开有几种按开关的方法)

1 1 1 (这3个灯笼变为开、开、开有几种按开关的方法)

很明显的高斯消元，与POJ 1830 开关问题几乎完全一样

本题是n个灯 m个开关(即 n个方程m个未知数)

P.s. 要记得每个Q都要对状态初始化！

 ][];
 ];

 int n;
 int Gauss(int n, int m)
 {
     , k, num=;
     ;k<n && col<m;k++, col++)
     {
         int max_r=k;
         ;i<n;i++)
             if(abs(a[i][col])>abs(a[max_r][col]))
                 max_r=i;
         if(max_r!=k)
             ;j++)
                 swap(a[k][j], a[max_r][j]);
         if(!a[k][col])
         {
             k--;
             free_x[num++]=col;
             continue;
         }
         ;i<n;i++)
             if(a[i][col])
                 ;j++)
                     a[i][j]^=a[k][j];
     }
     for(int i=k;i<n;i++)
         if(a[i][col])
             ;
     return m-k;
 }

 ][];
 int main()
 {
     ;
     scanf("%d", &t);
     while(t--)
     {
         memset(a, , sizeof(a));
         memset(b, , sizeof(b));
         int n, m;
         scanf("%d%d", &n, &m);
         ;i<m;i++)
         {
             int k;
             scanf("%d", &k);
             while(k--)
             {
                 int X;
                 scanf("%d", &X);
                 a[X-][i]=;
                 b[X-][i]=;
             }
         }
         int Q;
         scanf("%d", &Q);
         printf("Case %d:\n", ca++);
         while(Q--)
         {
             ;i<n;i++)
                 ;j<m;j++)
                     a[i][j]=b[i][j];
             ;i<n;i++)
                 scanf("%d", &a[i][m]);
             int t=Gauss(n, m);
             )
             {
                 puts(");
                 continue;
             }
             LL ans=1LL<<t;
             cout<<ans<<endl;
         }
     }
     ;
 }

HDOJ 3364

巴特西

[Gauss]HDOJ3364 Lanterns

最新文章

热门文章