【poj2947】高斯消元求解同模方程组【没有AC，存代码】

题意：

p start end
a1,a2......ap (1<=ai<=n)
第一行表示从星期start 到星期end 一共生产了p 件装饰物(工作的天数为end-start+1+7*x,
加7*x 是因为它可能生产很多周)，第二行表示这p 件装饰物的种类(可能出现相同的种类，
即ai=aj)。规定每件装饰物至少生产3 天，最多生产9 天。问每种装饰物需要生产的天数。
如果没有解，则输出“Inconsistent data.”，如果有多解，则输出“Multiple solutions.”，如果
只有唯一解，则输出每种装饰物需要生产的天数。

题解：

设每种装饰物需要生产的天数为xi(1<=i<=n)。每一个条件就相当于

给定了一个方程式，假设生产1 类装饰物a1 件、2 类装饰物a2 件、i 类装饰物ai 件所花费
的天数为b，则可以列出下列方程：
a1*x1+a2*x2+...an*xn = b (mod 7)
这样一共可以列出m个方程式，然后使用高斯消元来解。

感觉高斯消元求解同模方程组跟线性方程组很像。

如果求出了一组解（x1,x2.....xn），则（x1+mod,x2+mod,.....,xn+mod）也是一组解。

必定有一组解是xi都<mod的。

所以就在加减的时候都要mod。然后还有不能直接除，要求逆元。

放个模版（n个方程，m-1个未知数），跟上题浮点数不一样，这题是整数，所以要求最小公倍数：

 int gauss(int n,int m)

 {

     int i,j,k,l,r;

     for(i=,j=;j<=maxx(n,m-);j++)

     {

         r=i;

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

             if(myabs(a[k][j])>myabs(a[r][j])) r=k;

         if(a[r][j])

         {

             for(l=;l<=m;l++) swap(a[r][l],a[i][l]);

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

             {

                 if(a[l][j])

                 {

                     int x=lcm(a[l][j],a[i][j]);

                     int la=x/a[i][j];

                     int lb=x/a[l][j];

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

                     {

                         a[l][k]=((a[l][k]*lb-a[i][k]*la)%mod+mod)%mod;

                     }

                 }

             }

             i++;

         }

     }

     // output(n,m);printf("i = %d\n",i);

     for(j=minn(i,m);j<=n;j++)

         if(a[j][m]) return -;//无解

     if((i-)<(m-)) return ;//有无穷解

     //求解唯一解(不能除，求逆元)

     int b;

     for(i=m-;i>=;i--)

     {

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

             a[i][m]=((a[i][m]-a[j][m]*a[i][j])%mod+mod)%mod;

         b=quickpow(a[i][i],mod-,mod);

         a[i][m]=(a[i][m]*b)%mod;

         if(a[i][m]<) a[i][m]+=mod;

     }

     return ;

 }

代码：我真的不知道为什么wa了。。拍了一百年了。。

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<cmath>

 #include<iostream>

 #include<algorithm>

 using namespace std;

 const int N=;

 const int mod=;

 int a[N][N];

 char s1[],s2[];

 void output(int n,int m)

 {

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

     {

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

             printf("%d ",a[i][j]);

         printf("\n");

     }

     printf("\n");

 }

 int myabs(int x){return x> ? x:-x;}

 int minn(int x,int y){return x<y ? x:y;}

 int maxx(int x,int y){return x>y ? x:y;}

 int idx(char s[])

 {

     if(s[]=='M') return ;

     if(s[]=='T' && s[]=='U') return ;

     if(s[]=='W') return ;

     if(s[]=='T' && s[]=='H') return ;

     if(s[]=='F') return ;

     if(s[]=='S' && s[]=='A') return ;

     return ;

 }

 int gcd(int x,int y)

 {

     if(y==) return x;

     return gcd(y,x%y);

 }

 int quickpow(int x,int y,int mod)

 {

     int ans=;

     while(y)

     {

         if(y&) ans=(ans*x)%mod;

         x=x*x;

         y/=;

     }

     return ans;

 }

 int lcm(int x,int y)

 {

     if(!x && !y) return ;

     return x*y/gcd(x,y);

 }

 int gauss(int n,int m)

 {

     int i,j,k,l,r;

     for(i=,j=;j<=maxx(n,m-);j++)

     {

         r=i;

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

             if(myabs(a[k][j])>myabs(a[r][j])) r=k;

         if(a[r][j])

         {

             for(l=;l<=m;l++) swap(a[r][l],a[i][l]);

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

             {

                 if(a[l][j])

                 {

                     int x=lcm(a[l][j],a[i][j]);

                     int la=x/a[i][j];

                     int lb=x/a[l][j];

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

                     {

                         a[l][k]=((a[l][k]*lb-a[i][k]*la)%mod+mod)%mod;

                     }

                 }

             }

             i++;

         }

     }

     // output(n,m);printf("i = %d\n",i);

     for(j=minn(i,m);j<=n;j++)

         if(a[j][m]) return -;//无解

     if((i-)<(m-)) return ;//有无穷解

     //求解唯一解(不能除，求逆元)

     int b;

     for(i=m-;i>=;i--)

     {

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

             a[i][m]=((a[i][m]-a[j][m]*a[i][j])%mod+mod)%mod;

         b=quickpow(a[i][i],mod-,mod);

         a[i][m]=(a[i][m]*b)%mod;

         if(a[i][m]<) a[i][m]+=mod;

     }

     return ;

 }

 int main()

 {

     freopen("a.in","r",stdin);

     while()

     {

         int x,n,m,num;

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

         if(!n && !m) return ;

         memset(a,,sizeof(a));

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

         {

             scanf("%d%s%s",&num,s1,s2);

             a[i][n+]=((idx(s2)-idx(s1)+)%mod+mod)%mod;

             for(int j=;j<=num;j++)

             {

                 scanf("%d",&x);

                 a[i][x]++;

                 a[i][x]%=mod;

             }

         }

         // output(m,n+1);

         int flag=gauss(m,n+);

         if(flag==-) printf("Inconsistent data.\n");

         if(flag==)  printf("Multiple solutions.\n");

         if(flag==)

         {

             for(int i=;i<n;i++) printf("%d ",a[i][n+]);

             printf("%d\n",a[n][n+]);

         }

     }

     return ;

 }

巴特西

【poj2947】高斯消元求解同模方程组【没有AC，存代码】

最新文章

热门文章