http://poj.org/problem?id=2065 (题目链接)
题意
题意半天看不懂。。给你一个素数P(P<=30000)和一串长为n的字符串str[]。字母'*'代表0，字母a-z分别代表1-26，这n个字符所代表的数字分别代表f(1)、f(2)....f(n)。定义: ${f(k)=\sum_{i=0}^{n-1}{a_ik^i~(mod~p)}~(1<=k<=n,0<=a_i<P)}$，求a0、a1.....an-1。题目保证肯定有唯一解。
Solution
直接高斯消元，因为是模方程组所以除的时候求个逆元即可。
代码
// poj2065
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<map>
#define LL long long
#define inf 2147483640
#define Pi acos(-1,0)
#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
using namespace std; const int maxn=100;
int a[maxn][maxn],n,P;
char ch[maxn]; int power(int a,int b,int c) {
int res=1;
while (b) {
if (b&1) res=res*a%c;
b>>=1;a=a*a%c;
}
return res;
}
void Gauss() {
for (int r,i=1;i<=n;i++) {
r=i;
for (int j=i+1;j<=n;j++) if (abs(a[r][i])<abs(a[j][i])) r=j;
if (a[r][i]==0) continue;
if (r!=i) for (int j=1;j<=n+1;j++) swap(a[i][j],a[r][j]);
int inv=power(a[i][i],P-2,P);
for (int j=1;j<=n;j++) if (j!=i) {
for (int k=n+1;k>=i;k--)
a[j][k]=(a[j][k]-(a[j][i]*inv)%P*a[i][k]%P+P)%P;
}
}
} int main() {
int T;scanf("%d",&T);
while (T--) {
scanf("%d",&P);
scanf("%s",ch+1);
n=strlen(ch+1);
for (int i=1;i<=n;i++) {
int tmp=1;
for (int j=1;j<=n;j++) {
a[i][j]=tmp;
tmp=tmp*i%P;
}
a[i][n+1]=ch[i]=='*' ? 0 : ch[i]-'a'+1;
}
Gauss();
for (int i=1;i<=n;i++) {
if (a[i][i]==0) {printf("0 ");continue;}
int inv=power(a[i][i],P-2,P);
printf("%d ",inv*a[i][n+1]%P);
}
puts("");
}
return 0;
}