QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#18394 | #992. Number of Colorful Matchings | Realityang# | AC ✓ | 378ms | 13180kb | C++14 | 2.5kb | 2022-01-18 22:36:25 | 2022-05-04 18:17:44 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=510,mod=2;char c;
int n,a[N][N],A[N][N],B[N][N],I[N][N],p[N][N],xx,II=1;
int ksm(int x,int y){
int s=1;
while(y){
if(y&1)s=s*x%mod;
x=x*x%mod;
y>>=1;
}
return s;
}
void qk(int r,int x,int y){
int c=mod-B[x][y]*ksm(B[x][r],mod-2)%mod;
for(int i=1;i<=n;i++){
A[i][y]=(A[i][y]+c*A[i][r]%mod)%mod;
B[i][y]=(B[i][y]+c*B[i][r]%mod)%mod;
I[i][y]=(I[i][y]+c*I[i][r]%mod)%mod;
}
}
void B_I(){
for(int i=1;i<=n;i++){
int x=0;
for(;xx<=n;xx++){
for(int j=i;j<=n;j++)if(B[j][i]){x=j;break;}
if(x){swap(A[i],A[x]);swap(B[i],B[x]);swap(I[i],I[x]);break;}
for(int j=1;j<=n;j++)B[j][i]=A[j][i],A[j][i]=0;
for(int j=1;j<i;j++)qk(j,j,i);
}
for(int j=1;j<=n;j++)if(i!=j)qk(i,i,j);
for(int j=1;j<=n;j++)A[i][j]=A[i][j]*ksm(B[i][i],mod-2)%mod,I[i][j]=I[i][j]*ksm(B[i][i],mod-2)%mod;
}
}
void sI(){
for(int i=1;i<=n;i++){
int x=0;
for(int j=i;j<=n;j++)if(I[j][i]){x=j;break;}
if(!x)break;
swap(I[i],I[x]);
for(int j=i+1;j<=n;j++){
int c=mod-I[j][i]*ksm(I[i][i],mod-2)%mod;
for(int k=1;k<=n;k++)I[j][k]=(I[j][k]+c*I[i][k]%mod)%mod;
}
II=II*I[i][i]%mod;
}
}
void gauss(){
for(int i=2;i<=n;i++){
int x=0;
for(int j=i;j<=n;j++)if(a[j][i-1]){x=j;break;}
if(x==0)continue;
swap(a[i],a[x]);
for(int j=1;j<=n;j++)swap(a[j][i],a[j][x]);
int c=ksm(a[i][i-1],mod-2);
for(int j=i+1;j<=n;j++){
int kk=a[j][i-1]*c%mod;
for(int k=i-1;k<=n;k++)a[j][k]=(a[j][k]-kk*a[i][k]%mod+mod)%mod;
for(int k=1;k<=n;k++)a[k][i]=(a[k][i]+kk*a[k][j]%mod)%mod;
}
}
}
void an(){
p[0][0]=1;p[1][0]=mod-a[1][1];p[1][1]=1;
for(int i=2;i<=n;i++){
p[i][0]=p[i-1][0]*(mod-a[i][i])%mod;
for(int j=1;j<=n;j++)p[i][j]=(p[i-1][j-1]-p[i-1][j]*a[i][i]%mod+mod)%mod;
for(int m=1;m<=i-1;m++){
int tr=a[i-m][i];
for(int j=i-m+1;j<=i;j++)tr=tr*a[j][j-1]%mod;
for(int j=0;j<=n;j++)p[i][j]=(p[i][j]-tr*p[i-m-1][j]%mod+mod)%mod;
}
}
}
signed main(){
scanf("%lld\n",&n);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
scanf("%c",&c);
B[i][j]=c-'0';
}scanf("\n");
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
scanf("%c",&c);
A[i][j]=c-'0';
}if(i!=n)scanf("\n");
}
for(int i=1;i<=n;i++)I[i][i]=1;
B_I();sI();
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)a[i][j]=(mod-A[i][j])%mod;
gauss();an();II=ksm(II,mod-2);
for(int i=xx;i<=n;i++)printf("%lld\n",p[n][i]*II%mod);
for(int i=1;i<=xx;i++)printf("0\n");
}
詳細信息
Test #1:
score: 100
Accepted
time: 5ms
memory: 11996kb
input:
2 11 10 00 11
output:
0 0 1
result:
ok 3 tokens
Test #2:
score: 0
Accepted
time: 2ms
memory: 11888kb
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: 11960kb
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: 2ms
memory: 12028kb
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: 315ms
memory: 13112kb
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: 322ms
memory: 13092kb
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: 309ms
memory: 13180kb
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: 115ms
memory: 12844kb
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: 168ms
memory: 12908kb
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: 270ms
memory: 12924kb
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: 378ms
memory: 12292kb
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: 7ms
memory: 12088kb
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: 8ms
memory: 12316kb
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: 25ms
memory: 12452kb
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: 71ms
memory: 12640kb
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: 121ms
memory: 12868kb
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: 186ms
memory: 12976kb
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: 236ms
memory: 12988kb
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: 298ms
memory: 13112kb
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: 304ms
memory: 13156kb
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: 322ms
memory: 13024kb
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