HDU 3364 Lanterns Gauss消元

タイトルリンク: http://acm.hdu.edu.cn/showproblem.php?pid=3364
n個の提灯は初めはすべて消えて(0状態)、提灯の間の連動関係を知っていて、つまりある提灯が反転してそれと連動する提灯が反転することを牽引することができて、q回の尋問を与えて、毎回1種の提灯の目標の状態を表して、全部で何種類の目標の状態に達する方法数を聞きます.
分析:ガウス消元.POJ 1830スイッチの問題のアップグレード版.2つの点に注意してください:(1)方程式グループが解がない場合(すなわち目標状態に達することができない場合)出力0(この良い穴は、サンプルを見てから見えます);(2)n∈[1.50]のため,最終シナリオ数はintを超える可能性がありlong longで格納する.
実装コードは次のとおりです.

/*
     0
        k   
q   ，            
              
*/
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn=50;
int a[maxn][maxn+1],b[maxn][maxn+1],x[maxn],equ,var;
int pre[maxn]; //         
void Init()
{
    scanf("%d%d",&equ,&var);
    int k,tmp;
    memset(a,0,sizeof(a));
    memset(x,0,sizeof(x));
    for(int i=0;i<var;i++)
    {
        scanf("%d",&k);
        for(int j=0;j<k;j++)
        {
            scanf("%d",&tmp);
            a[tmp-1][i]=1;
        }
    }
}
void Debug()
{
    for(int i=0;i<equ;i++)
    {
        for(int j=0;j<=var;j++)
          cout<<a[i][j]<<" ";
        cout<<endl;
    }
    cout<<endl;
}
int gcd(int a,int b)
{
    if(a<0) return gcd(-a,b);
    if(b<0) return gcd(a,-b);
    return b==0?a:gcd(b,a%b);
}
void Gauss()
{
    int k,col=0;
    for(k=0;k<equ&&col<var;k++,col++)
    {
        int mx=k;
        for(int i=k+1;i<equ;i++)
           if(a[i][col]>a[mx][col]) mx=i;
        if(mx!=k)
        {
            for(int i=k;i<var+1;i++)
               swap(a[k][i],a[mx][i]);
        }
        if(!a[k][col])
        {
            k--; continue;
        }
        for(int i=k+1;i<equ;i++)
        if(a[i][col])
        {
            int lcm=a[k][col]/gcd(a[k][col],a[i][col])*a[i][col];
            int ta=lcm/a[i][col],tb=lcm/a[k][col];
            for(int j=col;j<var+1;j++)
               a[i][j]=((a[i][j]*ta-a[k][j]*tb)%2+2)%2;
        }
    }
    //Debug();
    for(int i=k;i<equ;i++)
      if(a[i][col])
      {
          puts("0"); //       0（  ）
          return ;
      }
    printf("%I64d
",1LL<<(var-k));
}
int main()
{
    int t,T=1,q;
    scanf("%d",&t);
    while(t--)
    {
        Init();
        scanf("%d",&q);
        for(int i=0;i<equ;i++)
          for(int j=0;j<=var;j++)
            b[i][j]=a[i][j];
        printf("Case %d:
",T++);
        while(q--)
        {
            for(int i=0;i<equ;i++)
              for(int j=0;j<=var;j++)
                a[i][j]=b[i][j];
            memset(x,0,sizeof(x));
            for(int i=0;i<equ;i++)
              scanf("%d",&a[i][var]);
            Gauss();
        }
    }
    return 0;
}