POJ 2065 - SETI

http://poj.org/problem?id=2065

概要

数列 \(a_0, \ldots, a_{n-1}\) と素数 \(p\) を用いて，関数 \(f(k)\) を \(f(k) = \sum_{0 \le i \le n-1} a_i k ^ i\) と定める． \(f(k)\) は \(1 \le k \le n\) に対して \(0 \le f(k) \le 26\) を満たすとする．

\(p\) と \(f(1), \ldots, f(n)\) の値が与えられるので，\(a_0, \ldots, a_{n-1}\) を答える．

制約

解法

\(a_{i}\) に関する連立方程式を \(\mbox{GF}(p)\) の上で解くだけ．

  1 #include <iostream>
  2 #include <vector>
  3 using namespace std;
  4 
  5 struct mod/*{{{*/
  6 {
  7   int m;
  8   vector<int> tbl;
  9   mod(int a) : m(a), tbl(m+1)
 10   {
 11     for (int x = 1; x < m; x++) {
 12       tbl[x] = pow(x, a-2);
 13     }
 14   }
 15   int pow(int x, int e)
 16   {
 17     if (e == 0) {
 18       return 1;
 19     } else if (e & 1) {
 20       return (x * pow(x, e-1))%m;
 21     } else {
 22       const int y = pow(x, e>>1);
 23       return (y*y)%m;
 24     }
 25   }
 26   int operator()(int x) const { return ((x%m)+m)%m; }
 27   int inv(int x) const { return tbl[x]; }
 28 };/*}}}*/
 29 
 30 vector<int> gaussian_elimination(vector<vector<int> > a, vector<int> b, const mod& M)/*{{{*/
 31 {
 32   const int N = a.size();
 33 
 34   for (int i = 0; i < N; i++) {
 35     for (int j = i+1; a[i][i] == 0 && j < N; j++) {
 36       swap(a[i], a[j]);
 37       swap(b[i], b[j]);
 38     }
 39     if (a[i][i] == 0) {
 40       continue;
 41     }
 42 
 43     const int t = M.inv(a[i][i]);
 44     for (int k = i; k < N; k++) {
 45       a[i][k] = M(a[i][k] * t);
 46     }
 47     b[i] = M(b[i] * t);
 48 
 49     for (int j = 0; j < N; j++) {
 50       if (i == j) {
 51         continue;
 52       }
 53       const int u = a[j][i];
 54       for (int k = i; k < N; k++) {
 55         a[j][k] = M(a[j][k] - u*a[i][k]);
 56       }
 57       b[j] = M(b[j] - u*b[i]);
 58     }
 59   }
 60 
 61   for (int i = 0; i < N; i++) {
 62     if (a[i][i] == 0 && b[i] != 0) {
 63       // no solution
 64       return vector<int>();
 65     }
 66   }
 67   return b;
 68 }/*}}}*/
 69 
 70 int main()
 71 {
 72   ios::sync_with_stdio(false);
 73   int T;
 74   cin >> T;
 75   while (T-- > 0) {
 76     int p;
 77     cin >> p;
 78     string s;
 79     cin >> s;
 80     const int N = s.size();
 81     mod m(p);
 82     vector<vector<int> > mat(N, vector<int>(N));
 83     vector<int> b(N);
 84     for (int i = 0; i < N; i++) {
 85       for (int j = 0; j < N; j++) {
 86         mat[i][j] = m.pow(i+1, j);
 87       }
 88       if (s[i] == '*') {
 89         b[i] = 0;
 90       } else {
 91         b[i] = s[i]-'a'+1;
 92       }
 93     }
 94 
 95     const vector<int> x = gaussian_elimination(mat, b, m);
 96     for (vector<int>::const_iterator it = x.begin(); it != x.end(); ++it) {
 97       if (it != x.begin()) {
 98         cout << " ";
 99       }
100       cout << *it;
101     }
102     cout << endl;
103   }
104   return 0;
105 }
poj/2065.cc