POJ 2065 SETI (高斯消元取模)

题意：

输入一个素数p和一个字符串s（只包含小写字母和‘*’）,字符串中每个字符对应一个数字，'*'对应0，‘a’对应1，‘b’对应2....

例如str[] = "abc", 那么说明 n=3, 字符串所对应的数列为1, 2, 3。

题目中定义了一个函数：

a0*1^0 + a1*1^1+a2*1^2+........+an-1*1^(n-1) = f(1)(mod p)， f(1) = str[0] = a = 1;
a0*2^0 + a1*2^1+a2*2^2+........+an-1*2^(n-1) = f(2) (mod p) ， f(2) = str[1] = b = 2;
..........
a0*n^0 + a1*n^1+a2*n^2+........+an-1*n^(n-1) = f(n) (mod p) ，f(n) = str[n-1] = ````

求出 a0,a1,a2....an-1.

感谢大神翻译。

分析:

除了题意有点难懂以外，没有什么，就是给了一个一个含有n个方程n个未知数的线性方程组，让求解。

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <cstdlib>
  5 #include <cmath>
  6 #include <algorithm>
  7 #define LL __int64
  8 const int maxn = 70+10;
  9 const int INF = 1<<28;
 10 using namespace std;
 11 int equ, var, fn;
 12 int a[maxn][maxn], x[maxn];
 13 bool free_x[maxn];
 14 
 15 int gcd(int a, int b)
 16 {
 17     return b==0?a:gcd(b, a%b);
 18 }
 19 int lcm(int a, int b)
 20 {
 21     return a*b/gcd(a, b);
 22 }
 23 int Gauss(int x_mo)
 24 {
 25     //int x_mo;
 26     //x_mo = 7;
 27     int i, j, k, max_r, col;
 28     int ta, tb, LCM, tmp, fx_num;
 29     int free_index;
 30     col = 0;
 31 
 32     for(k = 0; k<equ && col<var; k++, col++)
 33     {
 34         max_r = k;
 35         for(i = k+1; i < equ; i++)
 36             if(abs(a[i][col])>abs(a[max_r][col]))
 37                 max_r = i;
 38 
 39         if(max_r != k)
 40             for(j = k; j < var+1; j++)
 41                 swap(a[k][j], a[max_r][j]);
 42 
 43         if(a[k][col]==0)
 44         {
 45             k--;
 46             continue;
 47         }
 48         for(i = k+1; i < equ; i++)
 49         {
 50             if(a[i][col] != 0)
 51             {
 52                 LCM = lcm(abs(a[i][col]), abs(a[k][col]));
 53                 ta = LCM/abs(a[i][col]);
 54                 tb= LCM/abs(a[k][col]);
 55                 if(a[i][col]*a[k][col] < 0) tb = -tb;
 56 
 57                 for(j = col; j < var+1; j++)
 58                     a[i][j] = ((a[i][j]*ta - a[k][j]*tb)%x_mo+x_mo)%x_mo;
 59             }
 60         }
 61     }
 62     for(i = var-1; i >= 0; i--)
 63     {
 64         tmp = a[i][var];
 65         for(j = i+1; j < var; j++)
 66             if(a[i][j] != 0)
 67                 tmp = ((tmp-a[i][j]*x[j])%x_mo+x_mo)%x_mo;
 68 
 69         if(a[i][i]==0)
 70             x[i] = 0;
 71         else
 72         {
 73             //if(tmp%a[i][i] != 0) return -2;
 74             while(tmp%a[i][i]!=0) tmp += x_mo;
 75             x[i] = (tmp/a[i][i])%x_mo;
 76         }
 77     }
 78     return 0;
 79 }
 80 int check(char ch)
 81 {
 82     if(ch=='*') return 0;
 83     return ch-'a'+1;
 84 }
 85 int Pow(int tmp, int j, int x_mo)
 86 {
 87     int sum = 1;
 88     tmp %= x_mo;
 89     for(int i = 1; i <= j; i++)
 90     {
 91         sum *= tmp;
 92         sum %= x_mo;
 93     }
 94     return sum%x_mo;
 95 }
 96 int main()
 97 {
 98     int x_mo, i, j, t, len, n;
 99     char s[maxn];
100     scanf("%d", &t);
101     while(t--)
102     {
103         scanf("%d %s", &x_mo, s);
104         len = strlen(s);
105         n = len;
106         equ = n; var = n;
107         memset(a, 0, sizeof(a));
108         memset(x, 0, sizeof(x));
109         for(i = 0; i < n; i++)
110         a[i][n] = (check(s[i]))%x_mo; //按照题目要求
111         for(i = 0; i < n; i++)
112         {
113             int tmp = check(s[i]);
114             for(j = 0; j < n; j++)
115             {
116               a[i][j] = Pow(i+1, j, x_mo); //按照题目要求，由于直接求(i+1)^j会超int所以在计算的时候一直取模
117             }
118         }
119         fn = Gauss(x_mo);
120         for(i = 0; i < n; i++)
121         {
122             if(i == n-1) printf("%d
", x[i]);
123             else  printf("%d ", x[i]);
124         }
125     }
126     return 0;
127 }

POJ 2065 SETI (高斯消元 取模)

POJ 2065 SETI (高斯消元取模)