C++14(g++5.4) 解法, 执行用时: 486ms, 内存消耗: 2656K, 提交时间: 2020-01-22 20:17:04

#include <iostream>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cassert>
using namespace std;
const int mo=998244353;
int quick(int k1,int k2){
	int k3=1;
	while (k2){
		if (k2&1) k3=1ll*k3*k1%mo;
		k2>>=1; k1=1ll*k1*k1%mo;
	}
	return k3;
}
const int N=410;
int x[N][N<<1],y[N][N];
int n;
char A[N][N],B[N][N];
int solve(int n,int m){
	for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++) x[i][j]=(x[i][j]+mo)%mo;
	int pd=1;
	for (int i=1;i<=n;i++){
		int r=i;
		for (int j=i;j<=n;j++) if (x[j][i]){
			r=j; break;
		}
		if (r!=i){
			for (int j=1;j<=m;j++) swap(x[i][j],x[r][j]);
			pd=(mo-pd)%mo;
		}
		pd=1ll*pd*x[i][i]%mo;
		int rev=quick(x[i][i],mo-2);
		for (int j=1;j<=m;j++) x[i][j]=1ll*x[i][j]*rev%mo;
		for (int j=1;j<=n;j++)
			if (j!=i){
				int now=x[j][i];
				for (int k=1;k<=m;k++)
					x[j][k]=(x[j][k]-1ll*x[i][k]*now%mo+mo)%mo;
			}
	}
	return pd;
}
int main(){
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%s",A[i]+1);
	for (int i=1;i<=n;i++) scanf("%s",B[i]+1);
	for (int i=1;i<=n;i++){
		for (int j=1;j<=n;j++){
			if (A[i][j]=='1'){
				x[i][j]-=1; x[i][i]+=1;
			}
			if (B[i][j]=='1'&&A[i][j]=='1'){
				y[i][j]=mo-1; y[i][i]+=1;
			}
		}
	}
	n--;
	for (int i=1;i<=n;i++)
		for (int j=1;j<=n;j++) x[i][j+n]=0;
	for (int i=1;i<=n;i++) x[i][i+n]=1;
	int r=solve(n,(n<<1));
	assert(r);
	cerr<<r<<endl;
	int ans=0;
	for (int i=1;i<=n;++i)
		for (int j=1;j<=n;j++)
			ans=(ans+1ll*x[i][j+n]*y[i][j])%mo;
	ans=1ll*ans*r%mo;
	cout<<ans<<endl;
}

C++11(clang++ 3.9) 解法, 执行用时: 247ms, 内存消耗: 2684K, 提交时间: 2020-01-28 11:16:19

#include<bits/stdc++.h>
using namespace std; 
#define ll long long
const int N=405,P=998244353;
int n,l,ans,res,a[N][N*2],b[N][N];char c[N];
inline int pw(int a,int b){int r=1;for(;b;b>>=1,a=1ll*a*a%P)if(b&1)r=1ll*r*a%P;return r;}
int main()
{
	scanf("%d",&n);ans=1;
	for(int i=1;i<=n;i++){scanf("%s",c+1);for(int j=1;j<=n;j++)a[i][j]=c[j]-'0';}
	for(int i=1;i<=n;i++){scanf("%s",c+1);for(int j=1;j<=n;j++)b[i][j]=(c[j]-'0')&a[i][j];}
	for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(i!=j){a[i][i]+=a[i][j];a[i][j]=P-a[i][j];b[i][i]+=b[i][j];b[i][j]=P-b[i][j];}
	for(int i=1;i<n;i++)a[i][i+n]=1;
	for(int i=1,j;i<n;i++)
	{
		if(!a[i][i])
		{
			for(j=i;j<n;j++)if(a[j][i])break;
			for(int k=i;k<n*2;k++)swap(a[i][k],a[j][k]);
			ans=P-ans;
		}
		ans=1ll*ans*a[i][i]%P;int t=pw(a[i][i],P-2);
		for(int k=i;k<n*2;k++)a[i][k]=1ll*a[i][k]*t%P;
		for(j=1;j<n;j++)if(j!=i&&a[j][i])
		{
			t=a[j][i];
			for(int k=i;k<n*2;k++)a[j][k]=(a[j][k]+1ll*(P-t)*a[i][k])%P;
		}
	} 
	for(int i=1;i<n;i++)for(int j=1;j<n;j++)res=(res+1ll*b[i][j]*a[j][i+n])%P;
	printf("%d\n",1ll*ans*res%P);
	return 0;
}