首页 > 代码库 > 【poj2065】 SETI

【poj2065】 SETI

2024-08-29 23:35:10   218人阅读

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


联系
我们