QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#18109 | #992. Number of Colorful Matchings | JohnAlfnov# | AC ✓ | 56ms | 6344kb | C++14 | 2.6kb | 2022-01-16 11:24:58 | 2022-05-04 17:06:29 |
Judging History
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