首页 > 代码库 > POJ 2065 SETI (高斯消元 取模)

POJ 2065 SETI (高斯消元 取模)

2024-07-18 15:15:19   220人阅读

题目链接

题意：

输入一个素数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\n", x[i]);123             else  printf("%d ", x[i]);124         }125     }126     return 0;127 }

 


联系
我们