首页 > 代码库 > 【poj2947】高斯消元求解同模方程组【没有AC，存代码】
【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个方程式，然后使用高斯消元来解。
的天数为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个未知数），跟上题浮点数不一样，这题是整数，所以要求最小公倍数：
1 int gauss(int n,int m)
2 {
3 int i,j,k,l,r;
4 for(i=1,j=1;j<=maxx(n,m-1);j++)
5 {
6 r=i;
7 for(k=i+1;k<=n;k++)
8 if(myabs(a[k][j])>myabs(a[r][j])) r=k;
9 if(a[r][j])
10 {
11 for(l=1;l<=m;l++) swap(a[r][l],a[i][l]);
12 for(l=i+1;l<=n;l++)
13 {
14 if(a[l][j])
15 {
16 int x=lcm(a[l][j],a[i][j]);
17 int la=x/a[i][j];
18 int lb=x/a[l][j];
19 for(k=i;k<=m;k++)
20 {
21 a[l][k]=((a[l][k]*lb-a[i][k]*la)%mod+mod)%mod;
22 }
23 }
24 }
25 i++;
26 }
27 }
28 // output(n,m);printf("i = %d\n",i);
29 for(j=minn(i,m);j<=n;j++)
30 if(a[j][m]) return -1;//无解
31 if((i-1)<(m-1)) return 0;//有无穷解
32 //求解唯一解(不能除，求逆元)
33 int b;
34 for(i=m-1;i>=1;i--)
35 {
36 for(j=i+1;j<m;j++)
37 a[i][m]=((a[i][m]-a[j][m]*a[i][j])%mod+mod)%mod;
38 b=quickpow(a[i][i],mod-2,mod);
39 a[i][m]=(a[i][m]*b)%mod;
40 if(a[i][m]<3) a[i][m]+=mod;
41 }
42 return 1;
43 }
代码：我真的不知道为什么wa了。。拍了一百年了。。
1 #include<cstdio>
2 #include<cstdlib>
3 #include<cstring>
4 #include<cmath>
5 #include<iostream>
6 #include<algorithm>
7 using namespace std;
8
9 const int N=350;
10 const int mod=7;
11 int a[N][N];
12 char s1[10],s2[10];
13
14 void output(int n,int m)
15 {
16 for(int i=1;i<=n;i++)
17 {
18 for(int j=1;j<=m;j++)
19 printf("%d ",a[i][j]);
20 printf("\n");
21 }
22 printf("\n");
23 }
24
25 int myabs(int x){return x>0 ? x:-x;}
26 int minn(int x,int y){return x<y ? x:y;}
27 int maxx(int x,int y){return x>y ? x:y;}
28
29 int idx(char s[])
30 {
31 if(s[0]==‘M‘) return 1;
32 if(s[0]==‘T‘ && s[1]==‘U‘) return 2;
33 if(s[0]==‘W‘) return 3;
34 if(s[0]==‘T‘ && s[1]==‘H‘) return 4;
35 if(s[0]==‘F‘) return 5;
36 if(s[0]==‘S‘ && s[1]==‘A‘) return 6;
37 return 7;
38 }
39
40 int gcd(int x,int y)
41 {
42 if(y==0) return x;
43 return gcd(y,x%y);
44 }
45
46 int quickpow(int x,int y,int mod)
47 {
48 int ans=1;
49 while(y)
50 {
51 if(y&1) ans=(ans*x)%mod;
52 x=x*x;
53 y/=2;
54 }
55 return ans;
56 }
57
58 int lcm(int x,int y)
59 {
60 if(!x && !y) return 0;
61 return x*y/gcd(x,y);
62 }
63
64 int gauss(int n,int m)
65 {
66 int i,j,k,l,r;
67 for(i=1,j=1;j<=maxx(n,m-1);j++)
68 {
69 r=i;
70 for(k=i+1;k<=n;k++)
71 if(myabs(a[k][j])>myabs(a[r][j])) r=k;
72 if(a[r][j])
73 {
74 for(l=1;l<=m;l++) swap(a[r][l],a[i][l]);
75 for(l=i+1;l<=n;l++)
76 {
77 if(a[l][j])
78 {
79 int x=lcm(a[l][j],a[i][j]);
80 int la=x/a[i][j];
81 int lb=x/a[l][j];
82 for(k=i;k<=m;k++)
83 {
84 a[l][k]=((a[l][k]*lb-a[i][k]*la)%mod+mod)%mod;
85 }
86 }
87 }
88 i++;
89 }
90 }
91 // output(n,m);printf("i = %d\n",i);
92 for(j=minn(i,m);j<=n;j++)
93 if(a[j][m]) return -1;//无解
94 if((i-1)<(m-1)) return 0;//有无穷解
95 //求解唯一解(不能除，求逆元)
96 int b;
97 for(i=m-1;i>=1;i--)
98 {
99 for(j=i+1;j<m;j++)
100 a[i][m]=((a[i][m]-a[j][m]*a[i][j])%mod+mod)%mod;
101 b=quickpow(a[i][i],mod-2,mod);
102 a[i][m]=(a[i][m]*b)%mod;
103 if(a[i][m]<3) a[i][m]+=mod;
104 }
105 return 1;
106 }
107
108 int main()
109 {
110 freopen("a.in","r",stdin);
111 while(1)
112 {
113 int x,n,m,num;
114 scanf("%d%d",&n,&m);
115 if(!n && !m) return 0;
116 memset(a,0,sizeof(a));
117 for(int i=1;i<=m;i++)
118 {
119 scanf("%d%s%s",&num,s1,s2);
120 a[i][n+1]=((idx(s2)-idx(s1)+1)%mod+mod)%mod;
121 for(int j=1;j<=num;j++)
122 {
123 scanf("%d",&x);
124 a[i][x]++;
125 a[i][x]%=mod;
126 }
127 }
128 // output(m,n+1);
129 int flag=gauss(m,n+1);
130 if(flag==-1) printf("Inconsistent data.\n");
131 if(flag==0) printf("Multiple solutions.\n");
132 if(flag==1)
133 {
134 for(int i=1;i<n;i++) printf("%d ",a[i][n+1]);
135 printf("%d\n",a[n][n+1]);
136 }
137 }
138 return 0;
139 }
【poj2947】高斯消元求解同模方程组【没有AC，存代码】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。