poj 2065 还是gauss消元

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <iostream>
  4 #include <queue>
  5 #include <vector>
  6 #include <stack>
  7 #include <cmath>
  8 
  9 using namespace std;
 10 
 11 const int M = 10005;
 12 const int maxn = 1000000;
 13 typedef long long LL;
 14 
 15 int a[75][75];
 16 int x[75];
 17 char s[75];
 18 int equ,var,p;
 19 
 20 int gcd(int a,int b)
 21 {
 22     if(b == 0) return a;
 23     else return gcd(b,a%b);
 24 
 25 }
 26 
 27 int lcm(int a,int b)
 28 {
 29     return (a/gcd(a,b))*b;
 30 }
 31 
 32 void gauss()
 33 {
 34     int k,col = 0;
 35     for(k=0;k<equ&&col<var;k++,col++){
 36         int mx_r = k; //找最大的行
 37         for(int i=k+1;i<equ;i++){
 38             if(abs(a[i][col])>abs(a[mx_r][col])) mx_r = i;
 39         }
 40         if(mx_r != k){
 41             for(int i=k;i<=var;i++) swap(a[k][i],a[mx_r][i]);
 42         }
 43         if(a[k][col] == 0){ k--;continue;}
 44         for(int i=k+1;i<equ;i++){
 45             if(a[i][col] != 0){
 46                 int lc = lcm(abs(a[i][col]),abs(a[k][col]));
 47                 int ta = lc/abs(a[i][col]);
 48                 int tb = lc/abs(a[k][col]);
 49                 if(a[i][col]*a[k][col]<0) tb = -tb;
 50                 for(int j=col;j<=var;j++){
 51                    a[i][j] = ((a[i][j]*ta-a[k][j]*tb)%p+p)%p;
 52                 }
 53             }
 54         }
 55     }
 56     int temp;
 57     for(int i=var-1;i>=0;i--){
 58          temp = a[i][var];
 59         for(int j=i+1;j<var;j++){
 60             if(a[i][j] != 0) temp -= a[i][j]*x[j];
 61             temp = (temp%p+p)%p;
 62         }
 63         while(temp % a[i][i]!=0) temp+=p;
 64         x[i] = (temp/a[i][i])%p;
 65     }
 66     for(int i=0;i<var-1;i++){
 67         printf("%d ",x[i]);
 68     }
 69     printf("%d
",x[var-1]);
 70 }
 71 
 72 int pow_mod(int a,int n,int MOD)
 73 {
 74     int ret=1;
 75     int temp=a%MOD;
 76     while(n)
 77     {
 78         if(n&1){ret*=temp;ret%=MOD;}
 79         temp*=temp;
 80         temp%=MOD;
 81         n>>=1;
 82     }
 83     return ret;
 84 }
 85 
 86 void init()
 87 {
 88 
 89     memset(x,0,sizeof(x));
 90     memset(a,0,sizeof(a));
 91     memset(s,0,sizeof(s));
 92     scanf("%d",&p);
 93     scanf("%s",s);
 94     int len = strlen(s);
 95     equ = var = len;
 96     for(int i=0;i<len;i++){
 97         if(s[i] == '*') a[i][var] = 0;
 98         else a[i][var] = s[i]-'a'+1;
 99         for(int j=0;j<len;j++){
100             a[i][j] = pow_mod(i+1,j,p);
101         }
102     }
103 }
104 
105 
106 int main()
107 {
108     int t;
109     scanf("%d",&t);
110     while(t--){
111         init();
112         gauss();
113     }
114 
115     return 0;
116 }
View Code