"ambigious", "ambigous"の元ネタはこれではなくBroken Audio Signalのほう。
行列累乗して連立方程式するやつ。
#include<stdio.h> #include<algorithm> using namespace std; int b[510][510]; int c[510]; int tmp[510][510]; int A[510][510]; int main(){ int a; scanf("%d",&a); for(int i=0;i<a;i++)for(int j=0;j<a;j++)scanf("%d",&b[i][j]); for(int i=0;i<a;i++)scanf("%d",c+i); int T;scanf("%d",&T); for(int i=0;i<a;i++)A[i][i]=1; while(T){ if(T%2){ for(int i=0;i<a;i++)for(int j=0;j<a;j++)tmp[i][j]=0; for(int i=0;i<a;i++)for(int j=0;j<a;j++)for(int k=0;k<a;k++) tmp[i][j]^=(A[i][k]&b[k][j]); for(int i=0;i<a;i++)for(int j=0;j<a;j++)A[i][j]=tmp[i][j]; } T/=2; for(int i=0;i<a;i++)for(int j=0;j<a;j++)tmp[i][j]=0; for(int i=0;i<a;i++)for(int j=0;j<a;j++)for(int k=0;k<a;k++) tmp[i][j]^=(b[i][k]&b[k][j]); for(int i=0;i<a;i++)for(int j=0;j<a;j++)b[i][j]=tmp[i][j]; } for(int i=0;i<a;i++)for(int j=0;j<a;j++)b[i][j]=A[i][j]; for(int i=0;i<a;i++)b[i][a]=c[i]; /*for(int i=0;i<a;i++){ for(int j=0;j<=a;j++)printf("%d ",b[i][j]); printf("\n"); }*/ int now=0; for(int i=0;i<a;i++){ int at=-1; for(int j=now;j<a;j++){ if(b[j][i]){ at=j;break; } } if(!~at){ continue; } for(int j=0;j<=a;j++)swap(b[now][j],b[at][j]); for(int j=0;j<a;j++){ if(now==j)continue; if(b[j][i]){ for(int k=0;k<=a;k++){ b[j][k]^=b[now][k]; } } } now++; } if(now<a){ bool ok=true; for(int j=now;j<a;j++)if(b[j][a])ok=false; if(ok)printf("ambiguous\n"); else printf("none\n"); }else{ for(int i=0;i<a;i++){ if(i)printf(" "); printf("%d",b[i][a]); } printf("\n"); } }