POJ2065 SETI 高斯消元

欢迎访问~原文出处——博客园-zhouzhendong

去博客园看该题解

---

题目传送门 - POJ2065

---

题意概括

　　多组数据，首先输入一个T表示数据组数，然后，每次输入一个质数，表示模数，然后，给出一个长度为n的字符串，第i个位置的字符ch表示f(i)= ch == '*' ? 0 : ch-'a'+1

　　求解同余方程：（模数为p）

　　f(1)=1a+1a+...+1a

　　f(2)=2a+2a+...+2a

　　f(3)=3a+3a+...+3a

　　......

　　f(n)=na+na+...+na

　　即

　　f(k)=∑ak

---

题解

　　根据题目的输入构建方程，然后就是高斯消元的裸题了。

---

代码

#include <cstring>

#include <cstdio>

#include <algorithm>

#include <cstdlib>

#include <cmath>

using namespace std;

const int N=75;

int T,n,mod,a[N][N],x[N];

char ch[N];

int Pow(int x,int y){

	if (!y)

		return 1;

	int xx=Pow(x,y/2);

	xx=xx*xx%mod;

	if (y&1)

		xx=xx*x%mod;

	return xx;

}

int Inv(int x){

	return Pow(x,mod-2);

}

void Gauss(){

	int k,c;

	for (k=c=0;k<n&&c<n;k++,c++){

		int Mk=-1;

		for (int i=k;i<n;i++)

			if (a[i][c]){

				Mk=i;

				break;

			}

		if (Mk==-1){

			k--;

			continue;

		}

		if (Mk!=k)

			for (int i=c;i<=n;i++)

				swap(a[Mk][i],a[k][i]);

		for (int i=k+1;i<n;i++)

			for (int j=n;j>=c;j--)

				a[i][j]=(a[i][j]*a[k][c]-a[k][j]*a[i][c])%mod;

	}

	memset(x,0,sizeof x);

	for (int i=n-1;i>=0;i--){

		int tmp=a[i][n];

		for (int j=i+1;j<n;j++)

			tmp=(tmp-a[i][j]*x[j])%mod;

		tmp=tmp*Inv(a[i][i])%mod;

		x[i]=(tmp+mod)%mod;

	}

}

int main(){

	scanf("%d",&T);

	while (T--){

		scanf("%d%s",&mod,ch);

		n=strlen(ch);

		for (int i=0;i<n;i++)

			a[i][n]=ch[i]=='*'?0:((ch[i]-'a'+1)%mod);

		for (int i=0;i<n;i++){

			a[i][0]=1;

			for (int j=1;j<n;j++)

				a[i][j]=a[i][j-1]*(i+1)%mod;

		}

		Gauss();

		for (int i=0;i<n;i++)

			printf("%d ",x[i]);

		puts("");

	}

	return 0;

}