首页 > 代码库 > POJ2065 SETI(高斯消元 同模方程)
POJ2065 SETI(高斯消元 同模方程)
(a1 * 1^0 + a2 * 1^1 + ... an * 1^n - 1) % P = f1
....
(a1 * n^0 + a2 * n^1 + ... an - 1 * n ^ n - 1) % P = fn
消元中A[k][i] % A[i][i]不为0时将A[k][i]变为他们的最小公倍数，即整行都乘上lcm(A[k][i], A[i][i]) / A[k][i]，回代求解时使用逆元
#include<cstdio>#include<iostream>#include<cstdlib>#include<cstring>#include<string>#include<algorithm>#include<map>#include<queue>#include<vector>#include<cmath>#include<utility>using namespace std;typedef long long LL;const int N = 100, INF = 0x3F3F3F3F;int hs[256];int inv[50000];int p;LL a[N][N];template<typename T>T gcd(T a, T b){ while(b){ T t = a % b; a = b; b = t; } return a;}template<typename T>T lcm(T a, T b){ return a / gcd(a, b) * b;}template<typename T>void gauss_jordan(T A[N][N], int n){ for(int i = 0; i < n; i++){ //选择一行r与第i行交换 int r = i; for(int j = i; j < n; j++){ if(A[j][i]){ r = j; break; } } if(A[r][i] == 0){ continue; } if(r != i){ for(int j = 0; j <= n; j++){ swap(A[r][j], A[i][j]); } } for(int k = i + 1; k < n; k++){ if(A[k][i]){ if(A[k][i] % A[i][i]){ T d = lcm(A[k][i], A[i][i]) / A[k][i]; for(int j = i; j <= n; j++){ A[k][j] *= d; } } T d = A[k][i] / A[i][i] % p; for(int j = n; j >= i; j--){ A[k][j] -= d * A[i][j] % p; A[k][j] = (A[k][j] % p + p) % p; } } } } for(int i = n - 1; i >= 0; i--){ for(int j = i + 1; j < n; j++){ A[i][n] -= A[j][n] * A[i][j] % p; A[i][n] = (A[i][n] % p + p) % p; } A[i][n] = A[i][n] * inv[A[i][i] % p] % p; }}char str[N];int main(){ memset(hs, 0, sizeof(hs)); hs[‘*‘] = 0; for(int i = 0; i < 26; i++){ hs[i + ‘a‘] = i + 1; } int t; cin>>t; while(t--){ int n; cin>>p; cin>>str; inv[1] = 1; for(int i = 2; i < p; i++){ inv[i] = (p - p / i ) * inv[p % i] % p; } n = strlen(str); memset(a, 0, sizeof(a)); for(int i = 0; i < n; i++){ a[i][n] = hs[str[i]]; a[i][0] = 1; for(int j = 1; j < n; j++){ a[i][j] = a[i][j - 1] * (i + 1) % p; } } gauss_jordan(a, n); cout<<a[0][n]; for(int i = 1; i < n; i++){ cout<<‘ ‘<<a[i][n]; } cout<<endl; } return 0;}
POJ2065 SETI(高斯消元 同模方程)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。