QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#733698 | #5205. Game of Questions | ydzr00000 | AC ✓ | 455ms | 5492kb | C++17 | 1.3kb | 2024-11-10 20:32:09 | 2024-11-10 20:32:09 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
double dp[1<<17];
int buf[1<<17];
int main(){
int n,m;
scanf("%d %d",&n,&m);
for(int i=0;i<n;i++)
{
int sta=0;
for(int j=0;j<m;j++)
{
char ch;
cin>>ch;
if(ch=='1')
sta|=(1<<j);
}
buf[sta]++;
}
int full=(1<<m)-1;
dp[full]=1;
double ans=0;
int sta=full;
auto DP=[&](auto self,int id)->void
{
if(!id)
{
int cnt=0;
for(int g=((sta-1)&sta);g;g=(g-1)&sta)
cnt+=buf[g];
if(!cnt)
{
ans+=dp[sta];
return;
}
for(int g=((sta-1)&sta);g;g=(g-1)&sta)
dp[g]+=dp[sta]*buf[g]/cnt;
return;
}
self(self,id-1);
sta^=(1<<id);
for(int g=sta;;g=(g-1)&sta)
{
buf[g]+=buf[g|(1<<id)];
if(!g)
break;
}
self(self,id-1);
for(int g=sta;;g=(g-1)&sta)
{
buf[g]-=buf[g|(1<<id)];
if(!g)
break;
}
sta^=(1<<id);
};
DP(DP,m-1);
printf("%.12lf\n",ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3892kb
input:
1 5 11010
output:
1.000000000000
result:
ok found '1.000000000', expected '1.000000000', error '0.000000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3892kb
input:
3 3 011 101 110
output:
0.333333333333
result:
ok found '0.333333333', expected '0.333333333', error '0.000000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3896kb
input:
6 4 1011 0110 1111 0110 0000 1101
output:
0.166666666667
result:
ok found '0.166666667', expected '0.166666667', error '0.000000000'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3880kb
input:
1 2 00
output:
1.000000000000
result:
ok found '1.000000000', expected '1.000000000', error '0.000000000'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3888kb
input:
1 2 11
output:
1.000000000000
result:
ok found '1.000000000', expected '1.000000000', error '0.000000000'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3904kb
input:
2 5 10011 01111
output:
0.000000000000
result:
ok found '0.000000000', expected '0.000000000', error '-0.000000000'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3916kb
input:
5 2 11 11 11 01 10
output:
0.500000000000
result:
ok found '0.500000000', expected '0.500000000', error '0.000000000'
Test #8:
score: 0
Accepted
time: 1ms
memory: 3920kb
input:
10 10 0110100110 1100101110 1011100110 0011001011 1100101000 0010001001 1101100111 0000001101 1100000011 1100111100
output:
0.103009259259
result:
ok found '0.103009259', expected '0.103009259', error '0.000000000'
Test #9:
score: 0
Accepted
time: 1ms
memory: 3956kb
input:
100 10 1000101100 0011110101 1101010000 1011101011 0001000111 1110111101 1010001110 0000110111 1101110001 0000110010 1001111111 1010100001 1110000111 1111000111 1110101010 1101000101 1000010110 0110110100 0100001000 1000001001 0111100010 0100011110 0100111111 1000110000 0111010011 0110000100 1001101...
output:
0.118796767214
result:
ok found '0.118796767', expected '0.118796767', error '0.000000000'
Test #10:
score: 0
Accepted
time: 10ms
memory: 4004kb
input:
10000 13 0101111101110 1010110100101 1000011001110 0110001100100 1011011000111 0111111101111 0100111101111 1110001011100 0100011000110 0000110010101 0101100000111 0010010101001 1010001001100 0010101001100 1001011000010 0001101100001 0100111000011 1001100110111 0001001001111 1000000010101 00111000111...
output:
0.074748534063
result:
ok found '0.074748534', expected '0.074748534', error '0.000000000'
Test #11:
score: 0
Accepted
time: 90ms
memory: 4336kb
input:
100000 15 010101111010100 111100100000101 110010011010010 111000011011011 010101001100001 110111000011110 000011010000101 100100001001111 000101111001000 011101001000110 100011011110001 000111101100110 101110100000111 001000011011100 010011110010110 101111111100011 100110100000110 011101110100110 11...
output:
0.065734766331
result:
ok found '0.065734766', expected '0.065734766', error '0.000000000'
Test #12:
score: 0
Accepted
time: 231ms
memory: 4680kb
input:
200000 16 0001110111010101 1001011100001110 0001110100100111 0101000101000001 0010010011001011 0101111000000011 1011010000110001 1100111100101000 1110110100000100 0000010010110100 0101101101111100 0111001111001100 1000101011101010 0110100011001000 1010100111011100 0000101101010001 0010001011000000 0...
output:
0.062727405372
result:
ok found '0.062727405', expected '0.062727405', error '0.000000000'
Test #13:
score: 0
Accepted
time: 453ms
memory: 5428kb
input:
200000 17 11000001110100100 10101000100010101 00011000101010000 01111000011000100 11000111100001101 10101011010111000 00011011011001011 10110100010000110 11001111101010001 01010000110011100 01001011100111000 00011100110100010 11000100001100011 10011001100001111 11110110001001110 10001100000100110 11...
output:
0.058572616424
result:
ok found '0.058572616', expected '0.058572616', error '0.000000000'
Test #14:
score: 0
Accepted
time: 18ms
memory: 3952kb
input:
200000 2 10 11 11 01 01 11 00 01 10 00 10 00 11 00 00 11 00 01 01 10 11 01 11 10 11 11 01 01 10 10 00 00 01 11 10 01 10 10 10 10 11 00 00 10 11 01 10 11 10 10 00 10 01 11 00 11 01 01 10 11 01 01 01 00 11 10 10 10 11 11 10 01 10 00 00 01 00 00 10 01 01 01 01 00 00 11 11 00 10 10 11 11 00 00 01 10 00 ...
output:
0.500941261290
result:
ok found '0.500941261', expected '0.500941261', error '0.000000000'
Test #15:
score: 0
Accepted
time: 326ms
memory: 5432kb
input:
1 17 01011010000010110
output:
0.000000000000
result:
ok found '0.000000000', expected '0.000000000', error '-0.000000000'
Test #16:
score: 0
Accepted
time: 10ms
memory: 3956kb
input:
200000 2 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ...
output:
1.000000000000
result:
ok found '1.000000000', expected '1.000000000', error '0.000000000'
Test #17:
score: 0
Accepted
time: 232ms
memory: 4460kb
input:
1 17 00000000000000000
output:
1.000000000000
result:
ok found '1.000000000', expected '1.000000000', error '0.000000000'
Test #18:
score: 0
Accepted
time: 14ms
memory: 3864kb
input:
200000 2 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 11 ...
output:
1.000000000000
result:
ok found '1.000000000', expected '1.000000000', error '0.000000000'
Test #19:
score: 0
Accepted
time: 224ms
memory: 4400kb
input:
1 17 11111111111111111
output:
1.000000000000
result:
ok found '1.000000000', expected '1.000000000', error '0.000000000'
Test #20:
score: 0
Accepted
time: 326ms
memory: 4408kb
input:
200000 17 00000000000000000 00000000000000000 00000000000000000 00000000000000000 00000000000000000 00000000000000000 00000000000000000 00000000000000000 00000000000000000 00000000000000000 00000000000000000 00000000000000000 00000000000000000 00000000000000000 00000000000000000 00000000000000000 00...
output:
1.000000000000
result:
ok found '1.000000000', expected '1.000000000', error '0.000000000'
Test #21:
score: 0
Accepted
time: 428ms
memory: 5436kb
input:
200000 17 00000000000000000 00000000000000000 00000000000000000 00000000000000000 00000000000000000 00100000000000000 00010000000000000 00000000000000000 00000000000010000 00000000000000000 00000000000000000 00000000000000000 00000000000000000 00000000000000000 00000000001100000 00000000000000000 00...
output:
0.059148256607
result:
ok found '0.059148257', expected '0.059148257', error '0.000000000'
Test #22:
score: 0
Accepted
time: 426ms
memory: 5480kb
input:
200000 17 00000000000000000 00000000000000000 00000000000000000 00000000000000000 00000000010000000 00000000000100000 00000000000000000 00000000000000000 00000000000000000 00000000000000000 00010000000000000 10000000000000000 00000000000000000 00000000000000000 00000000010000000 00000001000100000 00...
output:
0.057211446454
result:
ok found '0.057211446', expected '0.057211446', error '0.000000000'
Test #23:
score: 0
Accepted
time: 433ms
memory: 5424kb
input:
200000 17 00100000010001001 00000000000000000 00000000000000000 00100100001000000 01010000000000001 00010000000000000 00000000000000000 00010000000000000 00000000000000000 00000000000000000 10000100000000000 00001000000000000 00000000000100000 00000000000000000 00000000000000000 00000000000010010 00...
output:
0.059417783155
result:
ok found '0.059417783', expected '0.059417783', error '0.000000000'
Test #24:
score: 0
Accepted
time: 432ms
memory: 5440kb
input:
200000 17 00100000100000000 00000100001000000 00100001000000010 01010000010001011 00000000000000000 00000011010010011 10011000000000000 00000000101001000 00000000101000000 00000000010100001 00000000000000000 00000000001000100 00000000111000010 00001000000000110 01001010000000000 00000001000000000 10...
output:
0.059216849922
result:
ok found '0.059216850', expected '0.059216850', error '0.000000000'
Test #25:
score: 0
Accepted
time: 439ms
memory: 5440kb
input:
200000 17 00000101010001001 00110001000001100 00001000000010001 10000100010000001 10000101000100000 10110000100100010 10010000111000000 00001000000000011 11100000000111100 10001000000010000 00101111000011010 10101000000000000 11001111000001000 00001000000010000 01000001100000111 10000001000111000 00...
output:
0.058793189979
result:
ok found '0.058793190', expected '0.058793190', error '0.000000000'
Test #26:
score: 0
Accepted
time: 448ms
memory: 5420kb
input:
200000 17 00000101000101000 01010001000101001 11110110110101110 11000011010010011 11000000100101000 10100000111101001 00001110101001100 00011010110001000 01101100011000010 10000110001101011 10000001000010000 11100000100100001 01011101001000001 00001001100000111 00010001111011100 11000110000111100 00...
output:
0.058908055488
result:
ok found '0.058908055', expected '0.058908055', error '0.000000000'
Test #27:
score: 0
Accepted
time: 455ms
memory: 5380kb
input:
200000 17 11011011001011010 11111101011101011 11010110101110011 00110101110010111 01011011010111010 01100011000000001 10101100111100011 01111110110100011 00110000011001111 01101010011010111 11010111110101011 01111110001110110 01110100100101111 10111000101110101 11111100111001101 00111111110101011 11...
output:
0.058816145260
result:
ok found '0.058816145', expected '0.058816145', error '0.000000000'
Test #28:
score: 0
Accepted
time: 441ms
memory: 5424kb
input:
200000 17 10011011100011010 01111101101011110 11101101111111101 01111111100101101 01010101110011111 00111111111111001 01111101111110011 11111110110111010 11111010111111111 11111111111111111 11011111011101111 10111011111101011 01110001101110110 11110101110111111 11111111010111100 11011001001110111 11...
output:
0.058630576020
result:
ok found '0.058630576', expected '0.058630576', error '0.000000000'
Test #29:
score: 0
Accepted
time: 434ms
memory: 5444kb
input:
200000 17 11111101111101111 11110111101111101 01111111011111111 10111111111101111 11110111111111111 11110110111010111 01110011111111111 11110110011110001 11111111001111111 01111111111111111 01111111110111111 11111111111101111 11011111111101111 01111111110110111 11111111101110101 11111111011101111 11...
output:
0.060236344825
result:
ok found '0.060236345', expected '0.060236345', error '0.000000000'
Test #30:
score: 0
Accepted
time: 429ms
memory: 5492kb
input:
200000 17 11111111011111111 01111111111111111 11111111111111111 11111111111111111 11111111111111111 11111111111111111 01011111110111111 10111111111111011 11111111111111111 11111111111111101 11111111101111111 11111111111001101 11111011111111111 11111111111111110 11011111111111111 11111111111111011 11...
output:
0.057955394337
result:
ok found '0.057955394', expected '0.057955394', error '0.000000000'
Test #31:
score: 0
Accepted
time: 431ms
memory: 5424kb
input:
200000 17 11111111111111111 11111111111111111 11111111111111111 11111111111111111 11111101111111111 11111111111111111 11111111111111111 11111111111111111 11111111111111111 11111111111111111 11011111111111111 11111111111111111 11111110111111111 11111111111111111 11111111111111111 11111111111111111 11...
output:
0.056681540367
result:
ok found '0.056681540', expected '0.056681540', error '0.000000000'
Test #32:
score: 0
Accepted
time: 428ms
memory: 5488kb
input:
200000 17 11111111111111111 11111111111111111 11110111111111111 11111111111111111 11111111111111111 11111111111111111 11111111111111111 11111111111111111 11111111111111111 11011111111111111 11111111111111111 11111111111111111 11111111111111111 11111111110111111 11111111111111111 11111111111111111 11...
output:
0.059233909027
result:
ok found '0.059233909', expected '0.059233909', error '0.000000000'
Test #33:
score: 0
Accepted
time: 323ms
memory: 4340kb
input:
200000 17 11111111111111111 11111111111111111 11111111111111111 11111111111111111 11111111111111111 11111111111111111 11111111111111111 11111111111111111 11111111111111111 11111111111111111 11111111111111111 11111111111111111 11111111111111111 11111111111111111 11111111111111111 11111111111111111 11...
output:
1.000000000000
result:
ok found '1.000000000', expected '1.000000000', error '0.000000000'