poj 2065SETI <高斯消元>

链接： http://poj.org/problem?id=2065

题意：

给你一个素数P(P<=30000)和一串长为n的字符串str[]。字母'*'代表0，字母a-z分别代表1-26，这n个字符所代表的数字分别代表f(1)、f(2)....f(n)。

定义: f (k) = ∑(0<=i<=n-1) a^iki (mod p) (1<=k<=n,0<=ai<P)

求a0、a1.....an-1

View Code

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 #include <string.h>
  4 #include <algorithm>
  5 using namespace std;
  6 int P, N;
  7 int d[100][100], x[100];
  8 int Gcd( int a, int b )
  9 {
 10     return b==0?a:Gcd( b, a%b );
 11 } 
 12 int Lcm( int a, int b )
 13 {
 14     return a/Gcd( a, b )*b;
 15 }
 16 int P_M( int a, int b, int m )
 17 {
 18     int ans=1, t=a%m;
 19     while( b ){
 20         if( b&1 )
 21             ans*=t;
 22         if( ans>m )ans%=m;
 23         b>>=1;
 24         t*=t;
 25         t%=m;
 26     }
 27     return ans; 
 28 }
 29 void Gauss(  )
 30 {
 31     int i=1, j, p, k, t;
 32     for( j=1; j<=N; ++ j ){    
 33     
 34         for( p=i; p<=N; ++ p ){
 35             if( d[p][j] )break;
 36         }    
 37         
 38         if( p>N )continue;
 39         if( p!=i ){
 40         
 41             for( k=j;k<=N+1; ++ k ){
 42                 t=d[p][j],d[p][j]=d[i][j], d[i][j]=t;
 43             }
 44         }
 45     
 46         for( p=i+1; p<=N; ++p ){
 47             if(d[p][j]){
 48                 int f1=Lcm( d[p][j], d[i][j] )/d[p][j];
 49                 int f2=Lcm( d[p][j], d[i][j] )/d[i][j];// 可以直接用f1=d[p][j],但是不能放在下面 一个for里面 
 50                 for(k=j; k<=N+1; ++k ){    
 51                     d[p][k] =(d[p][k]*f1-d[i][k]*f2)%P;
 52                 }
 53             }
 54         }
 55         ++i;
 56     }
 57     memset( x, 0, sizeof x );
 58     for( p=N; p>=1; --p ){
 59             int sum=0; 
 60             for(k=p+1; k<=N;++k ){
 61                 sum = ((sum+x[k]*d[p][k])%P+P)%P;
 62             }
 63             for( k=0;k<=P; ++k ){
 64                 if(( (d[p][p]*k)%P + P)%P== ((d[p][N+1]-sum)%P + P) % P){//同余方程求解 
 65                       x[p] = k;
 66                       break;
 67                 }
 68             } 
 69     }
 70     for( int i=1; i<=N; ++ i ){
 71         printf( "%d ", x[i] );    
 72     }
 73     puts( "" );
 74 }
 75 int main( )
 76 {
 77     int T;
 78     char s[100];
 79     scanf( "%d",&T );
 80     while( T-- ){
 81         scanf( "%d", &P );
 82         scanf( "%s", s);
 83         N=strlen( s );
 84         memset( d, 0, sizeof d );
 85         for( int i=0; i<N; ++ i ){
 86             if(s[i]=='*')d[i+1][N+1]=0;
 87             else d[i+1][N+1]=s[i]-'a'+1;
 88         }
 89         for( int i=1; i<=N; ++ i ){
 90             for( int j=1; j<=N; ++ j ){
 91                 d[i][j]=P_M( i, j-1 , P);
 92             }
 93         }/*
 94         for( int i=1; i<=N; ++ i )
 95         {
 96             for(int j=1; j<=N+1; ++ j)    
 97             {
 98                 printf( "%d ", d[i][j] );    
 99             }
100             puts( "" );
101         }*/
102         Gauss( );    
103         
104     
105     }
106     return 0;
107 }