【POJ】2065 SETI
题意：直接拿样例，37 abc。
a～z表示1～26，*表示0。
x0*1^0+x1*1^1+x2*1^2=1(mod 37)
x0*2^0+x1*2^1+x2*2^2=2(mod 37)
x0*3^0+x1*3^1+x2*3^2=3(mod 37)
高斯消元，除法x等于乘以x对p的逆元。
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #define MAXN 110 5 using namespace std; 6 char str[MAXN]; 7 int n, p; 8 int g[MAXN][MAXN], x[MAXN]; 9 int GET(char ch) { 10 if (ch == '*') 11 return 0; 12 return ch - 'a' + 1; 13 } 14 int PowMod(int a, int b, int c) { 15 int res; 16 for (res = 1; b; b >>= 1) { 17 if (b & 1) { 18 res *= a; 19 res %= c; 20 } 21 a *= a; 22 a %= c; 23 } 24 return res; 25 } 26 int EXTGCD(int a, int b, int &x, int &y) { 27 int t, d; 28 if (b == 0) { 29 x = 1; 30 y = 0; 31 return a; 32 } 33 d = EXTGCD(b, a % b, x, y); 34 t = x; 35 x = y; 36 y = t - a / b * y; 37 return d; 38 } 39 int Invmod(int a, int n) { 40 int x, y; 41 EXTGCD(a, n, x, y); 42 return (x % n + n) % n; 43 } 44 void Gauss() { 45 int i, j, k, tmp; 46 for (i = 0; i < n; i++) { 47 for (j = i; j < n; j++) { 48 if (g[j][i]) 49 break; 50 } 51 if (j != i) { 52 for (k = i; k <= n; k++) 53 swap(g[j][k], g[i][k]); 54 } 55 for (j = i + 1; j < n; j++) { 56 if (g[j][i]) { 57 tmp = (g[j][i] * Invmod(g[i][i], p)) % p; 58 for (k = i; k <= n; k++) { 59 g[j][k] -= tmp * g[i][k]; 60 g[j][k] = (g[j][k] % p + p) % p; 61 } 62 } 63 } 64 } 65 for (i = n - 1; i >= 0; i--) { 66 tmp = 0; 67 for (j = i + 1; j < n; j++) { 68 tmp += x[j] * g[i][j]; 69 tmp = (tmp % p + p) % p; 70 } 71 tmp = g[i][n] - tmp; 72 tmp = (tmp % p + p) % p; 73 x[i] = tmp * Invmod(g[i][i], p) % p; 74 } 75 } 76 int main() { 77 int c; 78 int i, j; 79 scanf("%d", &c); 80 while (c--) { 81 scanf("%d %s", &p, str); 82 n = strlen(str); 83 for (i = 0; i < n; i++) { 84 g[i][n] = GET(str[i]); 85 for (j = 0; j < n; j++) 86 g[i][j] = PowMod(i + 1, j, p); 87 } 88 Gauss(); 89 printf("%d", x[0]); 90 for (i = 1; i < n; i++) 91 printf(" %d", x[i]); 92 putchar('\n'); 93 } 94 return 0; 95 }优质内容筛选与推荐>>
1、Spark算子--partitionBy
2、04-AskDoctorForHelp-向医生寻求帮助
3、Android高手进阶必备
4、一家人，什么最重要？
5、宋体效果ExpandableListView模拟QQ好友列表