POJ 2065 SETI [高斯消元同余]

2019-04-13 13:04发布

站内文章 / 模拟电子
15665 0 1461
题意自己看，反正是裸题...
  普通高斯消元全换成模意义下行了 模模模！ #include #include #include #include #include using namespace std; const int N=100; inline int read(){ char c=getchar();int x=0,f=1; while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } typedef int Matrix[N][N]; int n,P; Matrix a; char s[N]; inline int Pow(int a,int b){ int re=1; for(;b;b>>=1,a=a*a%P) if(b&1) re=re*a%P; return re; } inline int Inv(int a){return Pow(a,P-2);} void ini(){memset(a,0,sizeof(a));} void Gauss(){ for(int i=1;i<=n;i++){ int j=i; while(j<=n&&!a[j][i]) j++; if(j!=i) for(int k=1;k<=n+1;k++) swap(a[i][k],a[j][k]); int inv=Inv(a[i][i]); for(int j=i+1;j<=n;j++){ int t=a[j][i]*inv%P; for(int k=i;k<=n+1;k++) a[j][k]=(a[j][k]-t*a[i][k]%P+P)%P; } } for(int i=n;i>=1;i--){ for(int j=n;j>i;j--) a[i][n+1]=(a[i][n+1]-a[j][n+1]*a[i][j]%P+P)%P; a[i][n+1]=a[i][n+1]*Inv(a[i][i])%P; } } void buildEquation(){ ini(); for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++) a[i][j]=Pow(i,j-1);//,printf("%d%c",a[i][j],j==n?' ':' '); a[i][n+1]=s[i]=='*'?0:s[i]-'a'+1; } } int main(){ freopen("in","r",stdin); int T=read(); while(T--){ P=read(); scanf("%s",s+1); n=strlen(s+1); buildEquation(); Gauss(); for(int i=1;i<=n;i++) printf("%d ",a[i][n+1]); puts(""); } }  

热门文章