QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#18303#992. Number of Colorful MatchingsWu_Ren#AC ✓57ms6508kbC++112.3kb2022-01-17 16:23:482022-05-04 17:47:49

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:47:49]
  • 评测
  • 测评结果:AC
  • 用时:57ms
  • 内存:6508kb
  • [2022-01-17 16:23:48]
  • 提交

answer

#include<bits/stdc++.h>
const int mod=2;
using namespace std;
int n,m,K,mul,ty;
int a[510][510],b[510][510],p[510][510];
char s[1000010];
void qmo(int &x){
	x+=(x>>31)&mod;
}
int ksm(int a,int k){
	int res=1;
	for(;k;k>>=1,a=1ll*a*a%mod) if(k&1) res=1ll*res*a%mod;
	return res;
}
void swapr(int a[][510],int x,int y){
	for(int k=1;k<=n;k++) swap(a[x][k],a[y][k]);
}
void addr(int a[][510],int x,int y,int z){
	for(int k=1;k<=n;k++) a[y][k]=(a[y][k]+1ll*a[x][k]*z)%mod;
}
void swapc(int a[][510],int x,int y){
	for(int k=1;k<=n;k++) swap(a[k][x],a[k][y]);
}
void addc(int a[][510],int x,int y,int z){
	for(int k=1;k<=n;k++) a[k][y]=(a[k][y]+1ll*a[k][x]*z)%mod;
}
void gauss(){
	mul=1,ty=0;
	for(int i=1;i<=n;i++){
		while(!b[i][i]){
			int j=i;
			while(!b[i][j]&&j<=n) j++;
			if(j<=n){
				swapc(a,i,j),swapc(b,i,j),qmo(mul=-mul);
				break;
			}
			ty++;
			if(ty>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++) if(b[i][j]) addr(a,j,i,mod-b[i][j]),addr(b,j,i,mod-b[i][j]);
		}
		if(ty>n) break;
		int inv=ksm(b[i][i],mod-2);mul=1ll*mul*b[i][i]%mod;
		for(int j=1;j<=n;j++) a[i][j]=1ll*a[i][j]*inv%mod,b[i][j]=1ll*b[i][j]*inv%mod;
		for(int j=1;j<=n;j++) if((i^j)&&b[j][i]) addr(a,i,j,mod-b[j][i]),addr(b,i,j,mod-b[j][i]);
	}
	for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) qmo(a[i][j]=-a[i][j]);
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%1d",&b[i][j]);
	for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%1d",&a[i][j]);
	gauss();
	for(int i=1;i<n;i++){
		int j=i+1;
		while(!a[j][i]&&j<=n) j++;
		if(j>n) continue;
		for(int k=1;k<=n;k++) swap(a[i+1][k],a[j][k]);
		for(int k=1;k<=n;k++) swap(a[k][i+1],a[k][j]);
		int inv=ksm(a[i+1][i],mod-2);
		for(int j=i+2;j<=n;j++) if(a[j][i]){
			int t=1ll*inv*a[j][i]%mod;
			for(int k=i;k<=n;k++) qmo(a[j][k]-=1ll*t*a[i+1][k]%mod);
			for(int k=1;k<=n;k++) a[k][i+1]=(a[k][i+1]+1ll*t*a[k][j])%mod;
		}
	}
	p[0][0]=1;
	for(int k=1;k<=n;k++){
		for(int i=1;i<=k;i++) p[k][i]=p[k-1][i-1];
		for(int i=0;i<=k;i++) qmo(p[k][i]-=1ll*a[k][k]*p[k-1][i]%mod);
		int nw=1,tp;
		for(int i=k-1;i;i--){
			nw=1ll*nw*a[i+1][i]%mod;
			tp=1ll*(mod-nw)*a[i][k]%mod;
			for(int j=0;j<=i;j++) p[k][j]=(p[k][j]+1ll*tp*p[i-1][j])%mod;
		}
	}
	for(int i=0;i<=n;i++) printf("%d\n",1ll*mul*p[n][min(n+1,i+ty)]%mod);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 5844kb

input:

2
11
10
00
11

output:

0
0
1

result:

ok 3 tokens

Test #2:

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

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: 0ms
memory: 5808kb

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: 0ms
memory: 5908kb

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: 57ms
memory: 6508kb

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: 57ms
memory: 6420kb

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: 57ms
memory: 6348kb

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: 10ms
memory: 6252kb

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: 15ms
memory: 6304kb

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: 33ms
memory: 6288kb

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: 38ms
memory: 6420kb

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: 5920kb

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: 5ms
memory: 5912kb

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: 9ms
memory: 6020kb

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: 17ms
memory: 6096kb

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: 6284kb

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: 34ms
memory: 6344kb

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: 43ms
memory: 6288kb

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: 57ms
memory: 6392kb

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: 56ms
memory: 6392kb

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: 57ms
memory: 6424kb

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