首页 > 代码库 > 【poj2065】 SETI
【poj2065】 SETI
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;}
【poj2065】 SETI
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。