QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#18109#992. Number of Colorful MatchingsJohnAlfnov#AC ✓56ms6344kbC++142.6kb2022-01-16 11:24:582022-05-04 17:06:29

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-05-04 17:06:29]
  • 评测
  • 测评结果:AC
  • 用时:56ms
  • 内存:6344kb
  • [2022-01-16 11:24:58]
  • 提交

answer

#include<bits/stdc++.h>
#define mod 2
using namespace std;
int n,a[505][505],b[505][505],f[505][505];
int gs,sg;
inline void swap_r(int x,int y){
	for(int i=1;i<=n;++i){
		swap(a[x][i],a[y][i]);
	}
}
inline void swap_c(int x,int y){
	for(int i=1;i<=n;++i){
		swap(a[i][x],a[i][y]);
	}
}
inline void add_r(int x,int y,int z){
	for(int i=1;i<=n;++i){
		a[y][i]=(a[y][i]+1ll*a[x][i]*z)%mod;
	}
}
inline void add_c(int x,int y,int z){
	for(int i=1;i<=n;++i){
		a[i][y]=(a[i][y]+1ll*a[i][x]*z)%mod;
	}
}
int Inver(int x){
	int ans=1,y=mod-2;
	while(y){
		if(y&1)ans=1ll*ans*x%mod;
		y>>=1,x=1ll*x*x%mod;
	}
	return ans;
}
void Add(int x,int y,int z){
	for(int i=1;i<=n;++i){
		a[y][i]=(a[y][i]+1ll*a[x][i]*z)%mod;
		b[y][i]=(b[y][i]+1ll*b[x][i]*z)%mod;
	}
}
void Gauss(){
	for(int i=1;i<=n;++i){
		while(!b[i][i]){
			for(int j=i+1;j<=n;++j)if(b[i][j]){
				sg=-sg;
				for(int k=1;k<=n;++k){
					swap(a[k][i],a[k][j]);
					swap(b[k][i],b[k][j]);
				}
				break;
			}
			if(!b[i][i]){
				++gs;
				if(gs>n)break;
				for(int j=1;j<=n;++j){
					b[i][j]=a[i][j];
					a[i][j]=0;
				}
				for(int j=1;j<i;++j){
					Add(j,i,-b[i][j]);
				}
			}
		}
		if(gs>n)break;
		int ny=Inver(b[i][i]);
		sg=1ll*sg*b[i][i]%mod;
		for(int j=1;j<=n;++j){
			a[i][j]=1ll*a[i][j]*ny%mod;
			b[i][j]=1ll*b[i][j]*ny%mod;
		}
		for(int j=1;j<=n;++j)if(j!=i&&b[j][i]){
			Add(i,j,-b[j][i]);
		}
	}
	for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)
		a[i][j]=-a[i][j];
}
void Hessenburg(){
	for(int i=1;i<n;++i){
		if(!a[i+1][i]){
			int flag=0;
			for(int j=i+2;j<=n;++j)if(a[j][i]){
				flag=1;
				swap_r(i+1,j);
				swap_c(i+1,j);
				break;
			}
			if(!flag)continue;
		}
		int x=Inver(a[i+1][i]);
		for(int j=i+2;j<=n;++j)if(a[j][i]){
			int xz=1ll*x*a[j][i]%mod;
			add_r(i+1,j,-xz);
			add_c(j,i+1,xz);
		}
	}
}
void Det(){
	f[0][0]=1;
	for(int i=1;i<=n;++i){
		for(int j=0;j<i;++j)
			f[i][j]=-1ll*a[i][i]*f[i-1][j]%mod;
		for(int j=1;j<=i;++j)
			f[i][j]=(f[i][j]+f[i-1][j-1])%mod;
		int S=-a[i][i-1];
		for(int j=i-2;j>=0;--j){
			int cs=1ll*S*a[j+1][i]%mod;
			for(int k=0;k<=j;++k)
				f[i][k]=(f[i][k]+1ll*f[j][k]*cs)%mod;
			S=1ll*S*a[j+1][j]%mod;
		}
	}
}
int main(){
	cin>>n;
	for(int i=1;i<=n;++i)for(int j=1;j<=n;++j){
		char cc;
		cin>>cc;
		b[i][j]=cc-'0';
	}
	for(int i=1;i<=n;++i)for(int j=1;j<=n;++j){
		char cc;
		cin>>cc;
		a[i][j]=cc-'0';
	}
	gs=0,sg=1;
	Gauss();
	Hessenburg();
	Det();
	for(int i=0;i<=n;++i){
		int aa=(1ll*sg*f[n][min(n+1,i+gs)]%mod+mod)%mod;
		printf("%d\n",aa);
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 5732kb

input:

2
11
10
00
11

output:

0
0
1

result:

ok 3 tokens

Test #2:

score: 0
Accepted
time: 1ms
memory: 3660kb

input:

10
0100110000
0000010111
0111000111
1000101100
1101000001
1111110000
1001001110
0000000011
0001000010
0100100110
1100010101
0001000001
0001001010
0011100111
0010101111
1001011011
1001100111
0111101001
0010100010
0001111011

output:

0
0
0
1
1
1
1
1
0
0
1

result:

ok 11 tokens

Test #3:

score: 0
Accepted
time: 3ms
memory: 3840kb

input:

18
001100000000010111
011100011110001011
001101000001111111
000010010011100000
000011000100001001
001001101100010101
000100000100010010
100011100111001010
111110010110111001
100111011110100100
101000100001111011
110000100101011111
101011001000000111
110001011110010101
110010011111001110
001001011100...

output:

0
0
0
1
0
0
0
1
1
1
1
1
1
1
0
0
0
0
0

result:

ok 19 tokens

Test #4:

score: 0
Accepted
time: 3ms
memory: 5748kb

input:

18
110000000001011101
110001111000101100
110100000111111100
001001001110000000
001100010000100100
100110110001010100
010000010001001010
001110011100101011
111001011011100110
011101111010010010
100010000111101111
000010010101111110
101100100000011111
000101111001010111
001001111100111000
100101110010...

output:

0
0
0
0
1
0
1
1
1
0
1
1
0
0
1
0
1
1
0

result:

ok 19 tokens

Test #5:

score: 0
Accepted
time: 55ms
memory: 5516kb

input:

300
00000000010111011100011110001011001101000001111111000010010011100000000011000100001001001001101100010101000100000100010010100011100111001010111110010110111001100111011110100100101000100001111011110000100101011111101011001000000111110001011110010101110010011111001110001001011100100010010000000000...

output:

0
0
0
0
0
1
1
1
0
1
1
1
0
0
0
1
1
0
1
0
0
1
1
0
0
0
0
1
0
0
0
1
1
0
1
0
1
0
1
0
1
1
1
0
0
1
0
0
1
1
1
1
0
0
0
1
1
0
1
1
1
0
0
1
1
1
1
0
1
1
0
0
1
0
1
1
0
0
1
1
1
1
1
0
0
1
0
0
1
1
0
1
0
1
0
0
1
0
0
1
1
1
1
1
0
1
1
0
0
1
1
0
0
1
1
0
1
1
1
1
0
1
0
0
0
0
1
1
0
0
0
0
1
0
0
1
1
0
1
1
1
0
1
1
0
0
1
0
1
1
...

result:

ok 301 tokens

Test #6:

score: 0
Accepted
time: 55ms
memory: 5508kb

input:

300
00000001011101110001111000101100110100000111111100001001001110000000001100010000100100100110110001010100010000010001001010001110011100101011111001011011100110011101111010010010100010000111101111000010010101111110101100100000011111000101111001010111001001111100111000100101110010001001000000000001...

output:

0
0
0
1
0
1
1
0
0
0
0
1
1
1
0
0
1
0
0
0
0
1
0
1
1
1
1
1
0
0
1
1
0
1
1
1
1
0
1
0
1
1
1
1
1
1
0
0
1
1
0
1
0
1
0
0
1
0
0
1
0
0
0
1
0
1
1
0
1
1
0
1
1
1
0
0
0
1
0
1
0
1
1
0
1
1
0
1
1
1
1
1
1
0
1
0
0
1
0
0
1
0
1
0
0
0
0
1
1
0
1
1
0
0
0
1
1
1
0
1
1
0
1
0
1
0
0
1
1
1
0
0
1
0
1
0
0
1
0
1
1
1
1
0
1
1
0
1
0
1
...

result:

ok 301 tokens

Test #7:

score: 0
Accepted
time: 51ms
memory: 6344kb

input:

300
00000101110111000111100010110011010000011111110000100100111000000000110001000010010010011011000101010001000001000100101000111001110010101111100101101110011001110111101001001010001000011110111100001001010111111010110010000001111100010111100101011100100111110011100010010111001000100100000000000111...

output:

0
0
0
0
0
1
1
1
1
0
0
0
1
1
1
0
1
0
0
1
0
1
1
0
1
0
1
0
0
1
1
0
0
0
0
0
1
1
0
0
0
0
1
0
1
1
1
1
1
1
1
0
1
0
0
1
0
0
1
1
0
1
1
1
0
1
0
1
0
1
0
1
0
1
0
0
0
1
0
0
1
1
1
0
0
0
0
0
0
1
0
0
0
0
1
1
1
1
0
0
0
0
1
0
1
1
0
1
0
1
0
1
0
0
0
0
1
0
1
1
1
0
0
0
0
1
1
0
1
1
1
0
1
1
0
0
1
1
1
0
0
0
1
0
0
1
0
1
1
1
...

result:

ok 301 tokens

Test #8:

score: 0
Accepted
time: 19ms
memory: 4932kb

input:

200
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

0
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 201 tokens

Test #9:

score: 0
Accepted
time: 22ms
memory: 5040kb

input:

230
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000...

output:

0
0
1
0
0
1
0
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 231 tokens

Test #10:

score: 0
Accepted
time: 34ms
memory: 6232kb

input:

270
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000...

output:

0
0
0
1
1
1
0
0
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 271 tokens

Test #11:

score: 0
Accepted
time: 52ms
memory: 5460kb

input:

300
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

0
1
0
0
0
1
1
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 301 tokens

Test #12:

score: 0
Accepted
time: 4ms
memory: 5816kb

input:

50
11000111100010110011010000011111110000100100111000
00000011000100001001001001101100010101000100000100
01001010001110011100101011111001011011100110011101
11101001001010001000011110111100001001010111111010
11001000000111110001011110010101110010011111001110
001001011100100010010000000000011101110101...

output:

0
1
1
1
0
0
0
0
0
0
1
0
0
1
1
1
0
1
0
0
0
1
0
0
0
1
1
1
0
0
1
1
0
0
1
0
1
0
0
1
0
1
0
1
1
1
1
0
0
1
1

result:

ok 51 tokens

Test #13:

score: 0
Accepted
time: 4ms
memory: 5840kb

input:

80
00011110001011001101000001111111000010010011100000000011000100001001001001101100
01010100010000010001001010001110011100101011111001011011100110011101111010010010
10001000011110111100001001010111111010110010000001111100010111100101011100100111
110011100010010111001000100100000000000111011101011011...

output:

0
1
0
0
1
0
1
0
1
0
0
1
1
0
0
0
0
1
1
0
0
0
1
1
1
0
1
1
1
0
0
0
1
1
1
0
0
0
0
1
1
0
0
1
0
1
0
1
0
0
1
0
1
1
1
1
1
1
0
1
1
0
1
1
1
1
1
0
0
0
0
0
1
0
0
1
0
1
1
0
0

result:

ok 81 tokens

Test #14:

score: 0
Accepted
time: 7ms
memory: 4384kb

input:

120
011110001011001101000001111111000010010011100000000011000100001001001001101100010101000100000100010010100011100111001010
111110010110111001100111011110100100101000100001111011110000100101011111101011001000000111110001011110010101110010011111
001110001001011100100010010000000000011101110101101110...

output:

0
1
0
0
1
0
1
0
0
1
1
0
0
0
1
1
0
1
0
0
0
0
0
1
1
1
0
1
0
0
0
0
1
1
0
1
1
0
0
1
1
1
0
1
1
1
0
0
0
1
0
1
0
1
1
1
1
1
0
1
0
0
1
0
1
1
0
1
0
1
1
0
1
1
1
1
1
0
1
1
0
0
0
0
0
0
0
0
0
0
1
0
0
1
0
0
1
1
0
1
1
1
0
1
0
1
0
1
0
0
0
1
0
1
0
0
1
0
0
0
0

result:

ok 121 tokens

Test #15:

score: 0
Accepted
time: 15ms
memory: 4752kb

input:

180
111000101100110100000111111100001001001110000000001100010000100100100110110001010100010000010001001010001110011100101011111001011011100110011101111010010010100010000111101111000010
0101011111101011001000000111110001011110010101110010011111001110001001011100100010010000000000011101110101101110100...

output:

0
1
0
0
1
1
1
1
0
1
1
0
1
0
0
0
1
1
0
0
0
0
0
1
1
1
0
0
1
1
0
0
0
1
1
1
1
0
1
1
1
0
0
1
1
0
1
1
1
0
0
0
1
0
0
1
0
1
0
1
1
1
0
0
0
1
0
1
1
1
1
0
0
0
0
0
1
1
1
0
0
1
1
1
1
1
0
0
0
0
0
0
1
1
0
1
0
1
1
0
0
1
1
1
1
0
0
0
1
0
1
0
1
1
0
1
0
1
0
0
1
1
1
1
0
1
1
1
1
0
0
1
0
1
1
1
0
1
1
0
1
1
1
1
1
0
0
0
1
1
...

result:

ok 181 tokens

Test #16:

score: 0
Accepted
time: 20ms
memory: 5032kb

input:

220
1000101100110100000111111100001001001110000000001100010000100100100110110001010100010000010001001010001110011100101011111001011011100110011101111010010010100010000111101111000010010101111110101100100000011111000101111001
010111001001111100111000100101110010001001000000000001110111010110111010011...

output:

1
0
0
0
0
0
1
1
0
1
0
0
0
1
1
1
1
1
1
0
1
1
0
0
1
1
1
0
0
0
0
0
0
1
1
1
0
1
0
1
0
1
1
0
0
1
0
1
0
1
1
0
0
1
1
0
1
1
1
0
1
1
0
1
1
1
1
0
0
0
1
0
1
1
1
1
0
0
0
1
0
1
1
0
1
1
1
1
1
0
0
0
0
1
1
0
0
0
0
0
1
0
0
0
0
1
0
0
0
1
1
1
1
1
0
0
1
1
0
0
0
0
0
1
1
1
0
0
0
1
1
0
1
1
1
1
1
1
1
0
1
0
1
0
0
1
1
0
1
0
...

result:

ok 221 tokens

Test #17:

score: 0
Accepted
time: 33ms
memory: 6300kb

input:

250
0010110011010000011111110000100100111000000000110001000010010010011011000101010001000001000100101000111001110010101111100101101110011001110111101001001010001000011110111100001001010111111010110010000001111100010111100101011100100111110011100010010111
001000100100000000000111011101011011101001111...

output:

0
1
1
1
0
1
1
0
0
1
1
0
1
0
0
0
1
0
0
1
1
0
0
1
1
1
0
1
0
0
0
0
1
0
0
0
0
1
1
1
1
0
0
1
0
1
1
1
1
1
0
1
1
0
1
0
0
0
1
0
0
0
0
0
1
0
1
1
0
1
1
0
0
1
1
1
0
1
0
0
1
0
0
1
0
1
0
0
1
0
1
1
1
1
1
1
1
0
1
1
1
1
1
0
1
1
0
1
0
1
1
1
0
0
1
0
0
0
1
1
0
1
1
1
1
0
1
1
0
0
1
1
0
1
1
1
1
0
0
0
0
1
1
1
0
1
1
0
1
0
...

result:

ok 251 tokens

Test #18:

score: 0
Accepted
time: 42ms
memory: 6200kb

input:

270
101100110100000111111100001001001110000000001100010000100100100110110001010100010000010001001010001110011100101011111001011011100110011101111010010010100010000111101111000010010101111110101100100000011111000101111001010111001001111100111000100101110010001001000000000001
1101110101101110100111111...

output:

0
1
0
0
1
1
1
0
0
1
0
1
0
1
1
0
1
1
0
0
1
0
0
1
1
1
0
1
1
0
0
0
1
0
0
1
1
1
0
0
0
0
1
0
0
0
0
0
1
1
1
0
1
1
1
0
0
1
1
0
1
1
1
1
0
1
1
0
0
1
0
0
0
1
1
0
0
1
1
1
1
0
1
0
0
1
0
1
0
0
1
1
1
1
0
0
0
1
0
1
0
0
1
0
0
0
1
1
0
0
1
1
0
1
1
1
1
0
1
1
0
0
0
0
1
0
0
1
1
0
0
0
0
0
0
1
1
0
0
1
0
1
1
0
0
0
0
1
0
0
...

result:

ok 271 tokens

Test #19:

score: 0
Accepted
time: 55ms
memory: 5512kb

input:

300
11001101000001111111000010010011100000000011000100001001001001101100010101000100000100010010100011100111001010111110010110111001100111011110100100101000100001111011110000100101011111101011001000000111110001011110010101110010011111001110001001011100100010010000000000011101110101101110100111111110...

output:

0
0
0
0
1
0
1
0
0
1
1
1
1
0
0
1
1
0
1
1
0
0
0
1
1
0
0
1
0
0
1
1
0
1
0
0
1
0
0
1
1
1
0
0
0
1
1
1
1
1
1
1
0
0
1
0
0
1
0
1
0
0
1
0
1
1
0
1
0
1
1
0
0
0
0
1
1
1
0
0
1
0
1
1
0
1
1
0
1
1
0
1
0
1
1
1
1
0
0
1
1
1
1
1
1
1
1
1
0
1
0
0
1
0
1
0
1
0
1
1
1
1
0
0
1
1
0
1
0
1
1
1
0
1
0
1
1
1
1
0
1
1
1
1
1
0
1
1
0
1
...

result:

ok 301 tokens

Test #20:

score: 0
Accepted
time: 46ms
memory: 6316kb

input:

300
00110100000111111100001001001110000000001100010000100100100110110001010100010000010001001010001110011100101011111001011011100110011101111010010010100010000111101111000010010101111110101100100000011111000101111001010111001001111100111000100101110010001001000000000001110111010110111010011111111010...

output:

1
1
0
1
1
0
1
1
1
1
1
1
1
0
0
1
0
1
0
1
0
0
1
1
0
0
1
0
0
0
0
0
1
0
0
1
1
1
0
0
0
1
1
0
0
1
0
1
0
1
0
1
0
0
0
1
0
0
1
0
0
0
0
0
0
0
1
0
1
1
0
0
1
0
0
1
0
0
1
1
1
0
0
0
1
1
0
1
0
1
0
0
0
0
0
0
0
1
0
0
1
1
1
1
0
1
0
0
0
1
0
1
0
1
1
0
0
0
1
1
0
1
1
0
0
0
0
1
0
1
0
1
0
0
0
0
0
1
1
0
0
0
0
1
0
0
0
0
0
0
...

result:

ok 301 tokens

Test #21:

score: 0
Accepted
time: 56ms
memory: 5540kb

input:

300
11010000011111110000100100111000000000110001000010010010011011000101010001000001000100101000111001110010101111100101101110011001110111101001001010001000011110111100001001010111111010110010000001111100010111100101011100100111110011100010010111001000100100000000000111011101011011101001111111101001...

output:

0
1
0
1
0
1
1
0
1
1
0
0
0
0
1
1
1
0
1
1
0
0
1
1
0
0
0
1
0
0
0
1
1
0
1
1
1
0
1
1
1
1
1
0
0
0
1
1
0
0
0
0
0
0
1
1
0
1
0
1
1
0
0
0
1
1
1
0
0
1
0
0
1
0
0
1
1
0
0
1
0
0
0
1
0
1
1
0
0
1
0
1
0
0
0
1
1
0
1
0
1
0
0
1
0
1
1
1
1
1
0
0
0
0
0
0
0
1
0
1
0
1
0
1
1
0
0
1
0
0
1
0
0
1
0
1
1
0
0
1
0
0
1
0
1
0
0
1
0
0
...

result:

ok 301 tokens