QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#819521 | #5205. Game of Questions | nullptr_qwq | AC ✓ | 102ms | 16788kb | C++14 | 2.1kb | 2024-12-18 16:10:03 | 2024-12-18 16:10:04 |
Judging History
answer
// Problem: G. Game of Questions
// Contest: Codeforces - 2022-2023 ICPC, NERC, Northern Eurasia Onsite (Unrated, Online Mirror, ICPC Rules, Teams Preferred)
// URL: https://codeforces.com/problemset/problem/1773/G
// Memory Limit: 1024 MB
// Time Limit: 5000 ms
//
// Powered by CP Editor (https://cpeditor.org)
// 私は猫です
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pb push_back
#define mkp make_pair
#define fi first
#define se second
#define inf 1000000000
#define infll 1000000000000000000ll
#define pii pair<int,int>
#define rep(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
#define per(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
#define F(i,a,b) for(int i=a,i##end=b;i<=i##end;i++)
#define dF(i,a,b) for(int i=a,i##end=b;i>=i##end;i--)
#define cmh(sjy) while(sjy--)
#define lowbit(x) (x&(-x))
#define HH printf("\n")
#define eb emplace_back
#define poly vector<int>
#define SZ(x) ((int)x.size())
using namespace std;
template<typename T>inline void chkmax(T &x,const T &y){ x=std::max(x,y); }
template<typename T>inline void chkmin(T &x,const T &y){ x=std::min(x,y); }
const int mod=998244353,maxn=500005;
int n,zsy,mx,c1[maxn],c2[maxn],sum[maxn],c[maxn];
double f[maxn],dp[maxn],g[maxn];
void FMT(double *f,int op){
F(i,0,n-1)F(s,0,mx)if((s>>i)&1){
if(op>0)f[s^(1<<i)]+=f[s];
else f[s^(1<<i)]-=f[s];
}
}
void solve(){
cin>>zsy>>n,dp[mx=(1<<n)-1]=1;
F(_,1,zsy){
string str; cin>>str;
int s=0; F(i,0,n-1)if(str[i]=='1')s^=(1<<i);
++c1[s],++c2[mx^s],++c[s],f[s]+=1;
} FMT(f,1);
double ans=0;
F(i,0,n-1)F(s,0,mx)if((s>>i)&1)c1[s]+=c1[s^(1<<i)],c2[s]+=c2[s^(1<<i)];
dF(i,n,1){
F(s,0,mx)g[s]=0;
F(s,0,mx)if(__builtin_popcount(s)==i){
const int num=zsy-c1[mx^s]-c2[mx^s];
if(num)g[s]=dp[s]/num;
if(!num&&(s&1))ans+=dp[s];
} FMT(g,1);
F(s,0,mx)g[s]*=f[s];
FMT(g,-1);
F(s,1,mx)if(__builtin_popcount(s)<i)dp[s]+=g[s];
}
cout<<fixed<<setprecision(12)<<ans;
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int zsy=1;
F(____,1,zsy)solve();
}
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 9900kb
input:
1 5 11010
output:
1.000000000000
result:
ok found '1.000000000', expected '1.000000000', error '0.000000000'
Test #2:
score: 0
Accepted
time: 2ms
memory: 11952kb
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: 11964kb
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: 11952kb
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: 12076kb
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: 11900kb
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: 11952kb
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: 0ms
memory: 12068kb
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: 0ms
memory: 12096kb
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: 3ms
memory: 12116kb
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: 25ms
memory: 12588kb
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: 54ms
memory: 11116kb
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: 99ms
memory: 14004kb
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: 9ms
memory: 12196kb
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: 63ms
memory: 16656kb
input:
1 17 01011010000010110
output:
0.000000000000
result:
ok found '0.000000000', expected '0.000000000', error '-0.000000000'
Test #16:
score: 0
Accepted
time: 3ms
memory: 11960kb
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: 63ms
memory: 12448kb
input:
1 17 00000000000000000
output:
1.000000000000
result:
ok found '1.000000000', expected '1.000000000', error '0.000000000'
Test #18:
score: 0
Accepted
time: 3ms
memory: 11976kb
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: 63ms
memory: 16100kb
input:
1 17 11111111111111111
output:
1.000000000000
result:
ok found '1.000000000', expected '1.000000000', error '0.000000000'
Test #20:
score: 0
Accepted
time: 76ms
memory: 16788kb
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: 82ms
memory: 16656kb
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: 72ms
memory: 14292kb
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: 81ms
memory: 15584kb
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: 82ms
memory: 16040kb
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: 88ms
memory: 15684kb
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: 95ms
memory: 16452kb
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: 102ms
memory: 14280kb
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: 84ms
memory: 16612kb
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: 86ms
memory: 14380kb
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: 80ms
memory: 16268kb
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: 79ms
memory: 15984kb
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: 75ms
memory: 15972kb
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: 76ms
memory: 12692kb
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'