QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#132673 | #5205. Game of Questions | Swarthmore# | AC ✓ | 361ms | 21004kb | C++17 | 3.8kb | 2023-07-31 01:04:45 | 2023-07-31 01:04:48 |
Judging History
answer
#include "bits/stdc++.h"
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
template<class T> using pq = priority_queue<T>;
template<class T> using pqg = priority_queue<T, vector<T>, greater<T>>;
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
#define trav(a,x) for (auto& a : x)
#define uid(a, b) uniform_int_distribution<int>(a, b)(rng)
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define ins insert
template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef DEBUG
#define dbg(x...) cerr << "\e[91m"<<__func__<<":"<<__LINE__<<" [" << #x << "] = ["; _print(x); cerr << "\e[39m" << endl;
#else
#define dbg(x...)
#endif
const int MOD = 1000000007;
const char nl = '\n';
const int MX = 17;
int N;
int cnt[1<<MX];
double dp[1<<MX];
int cm = 0;
double ans = 0;
void rem(int b) {
cm ^= 1<<b;
for (int s = cm; ; s = (s-1)&cm) {
cnt[s] += cnt[s|(1<<b)];
if (s == 0) break;
}
}
void add(int b) {
for (int s = cm; ; s = (s-1)&cm) {
cnt[s] -= cnt[s|(1<<b)];
if (s == 0) break;
}
cm ^= 1<<b;
}
void go(int b) {
if (b == -1) {
int cur = 0;
for (int s = (cm-1)&cm; s; s = (s-1)&cm) {
cur += cnt[s];
}
if (cur == 0) {
if (cm & (1<<(N-1))) ans += dp[cm];
return;
}
for (int s = (cm-1)&cm; s; s = (s-1)&cm) {
dp[s] += dp[cm] * cnt[s] / cur;
}
return;
}
go(b-1);
rem(b);
go(b-1);
add(b);
}
void solve() {
int M; cin >> M >> N;
string S[M]; F0R(i, M) cin >> S[i];
F0R(i, M) {
int cur = 0;
F0R(j, N) {
cur *= 2; cur += S[i][j] - '0';
}
cnt[cur]++;
}
dp[(1<<N)-1] = 1;
cm = (1<<N)-1;
go(N-2);
cout << setprecision(30) << ans << nl;
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
int T = 1;
// cin >> T;
while(T--) {
solve();
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3724kb
input:
1 5 11010
output:
1
result:
ok found '1.000000000', expected '1.000000000', error '0.000000000'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3848kb
input:
3 3 011 101 110
output:
0.333333333333333314829616256247
result:
ok found '0.333333333', expected '0.333333333', error '0.000000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3740kb
input:
6 4 1011 0110 1111 0110 0000 1101
output:
0.166666666666666657414808128124
result:
ok found '0.166666667', expected '0.166666667', error '0.000000000'
Test #4:
score: 0
Accepted
time: 1ms
memory: 3720kb
input:
1 2 00
output:
1
result:
ok found '1.000000000', expected '1.000000000', error '0.000000000'
Test #5:
score: 0
Accepted
time: 1ms
memory: 3676kb
input:
1 2 11
output:
1
result:
ok found '1.000000000', expected '1.000000000', error '0.000000000'
Test #6:
score: 0
Accepted
time: 1ms
memory: 3740kb
input:
2 5 10011 01111
output:
0
result:
ok found '0.000000000', expected '0.000000000', error '-0.000000000'
Test #7:
score: 0
Accepted
time: 1ms
memory: 3784kb
input:
5 2 11 11 11 01 10
output:
0.5
result:
ok found '0.500000000', expected '0.500000000', error '0.000000000'
Test #8:
score: 0
Accepted
time: 1ms
memory: 3864kb
input:
10 10 0110100110 1100101110 1011100110 0011001011 1100101000 0010001001 1101100111 0000001101 1100000011 1100111100
output:
0.103009259259259272623054926044
result:
ok found '0.103009259', expected '0.103009259', error '0.000000000'
Test #9:
score: 0
Accepted
time: 1ms
memory: 3808kb
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.118796767213537171614667897757
result:
ok found '0.118796767', expected '0.118796767', error '0.000000000'
Test #10:
score: 0
Accepted
time: 3ms
memory: 4252kb
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.0747485340626522776208418008537
result:
ok found '0.074748534', expected '0.074748534', error '0.000000000'
Test #11:
score: 0
Accepted
time: 43ms
memory: 7300kb
input:
100000 15 010101111010100 111100100000101 110010011010010 111000011011011 010101001100001 110111000011110 000011010000101 100100001001111 000101111001000 011101001000110 100011011110001 000111101100110 101110100000111 001000011011100 010011110010110 101111111100011 100110100000110 011101110100110 11...
output:
0.0657347663309566787592785885863
result:
ok found '0.065734766', expected '0.065734766', error '0.000000000'
Test #12:
score: 0
Accepted
time: 121ms
memory: 20240kb
input:
200000 16 0001110111010101 1001011100001110 0001110100100111 0101000101000001 0010010011001011 0101111000000011 1011010000110001 1100111100101000 1110110100000100 0000010010110100 0101101101111100 0111001111001100 1000101011101010 0110100011001000 1010100111011100 0000101101010001 0010001011000000 0...
output:
0.0627274053722708391234164082562
result:
ok found '0.062727405', expected '0.062727405', error '0.000000000'
Test #13:
score: 0
Accepted
time: 344ms
memory: 20884kb
input:
200000 17 11000001110100100 10101000100010101 00011000101010000 01111000011000100 11000111100001101 10101011010111000 00011011011001011 10110100010000110 11001111101010001 01010000110011100 01001011100111000 00011100110100010 11000100001100011 10011001100001111 11110110001001110 10001100000100110 11...
output:
0.0585726164238839150377735620623
result:
ok found '0.058572616', expected '0.058572616', error '0.000000000'
Test #14:
score: 0
Accepted
time: 4ms
memory: 10076kb
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.500941261290128725391923580901
result:
ok found '0.500941261', expected '0.500941261', error '0.000000000'
Test #15:
score: 0
Accepted
time: 333ms
memory: 5264kb
input:
1 17 01011010000010110
output:
0
result:
ok found '0.000000000', expected '0.000000000', error '-0.000000000'
Test #16:
score: 0
Accepted
time: 7ms
memory: 9928kb
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
result:
ok found '1.000000000', expected '1.000000000', error '0.000000000'
Test #17:
score: 0
Accepted
time: 230ms
memory: 4228kb
input:
1 17 00000000000000000
output:
1
result:
ok found '1.000000000', expected '1.000000000', error '0.000000000'
Test #18:
score: 0
Accepted
time: 9ms
memory: 9968kb
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
result:
ok found '1.000000000', expected '1.000000000', error '0.000000000'
Test #19:
score: 0
Accepted
time: 230ms
memory: 4324kb
input:
1 17 11111111111111111
output:
1
result:
ok found '1.000000000', expected '1.000000000', error '0.000000000'
Test #20:
score: 0
Accepted
time: 248ms
memory: 19844kb
input:
200000 17 00000000000000000 00000000000000000 00000000000000000 00000000000000000 00000000000000000 00000000000000000 00000000000000000 00000000000000000 00000000000000000 00000000000000000 00000000000000000 00000000000000000 00000000000000000 00000000000000000 00000000000000000 00000000000000000 00...
output:
1
result:
ok found '1.000000000', expected '1.000000000', error '0.000000000'
Test #21:
score: 0
Accepted
time: 355ms
memory: 20832kb
input:
200000 17 00000000000000000 00000000000000000 00000000000000000 00000000000000000 00000000000000000 00100000000000000 00010000000000000 00000000000000000 00000000000010000 00000000000000000 00000000000000000 00000000000000000 00000000000000000 00000000000000000 00000000001100000 00000000000000000 00...
output:
0.0591482566069235146666294156148
result:
ok found '0.059148257', expected '0.059148257', error '0.000000000'
Test #22:
score: 0
Accepted
time: 347ms
memory: 20868kb
input:
200000 17 00000000000000000 00000000000000000 00000000000000000 00000000000000000 00000000010000000 00000000000100000 00000000000000000 00000000000000000 00000000000000000 00000000000000000 00010000000000000 10000000000000000 00000000000000000 00000000000000000 00000000010000000 00000001000100000 00...
output:
0.0572114464535903657904647445775
result:
ok found '0.057211446', expected '0.057211446', error '0.000000000'
Test #23:
score: 0
Accepted
time: 341ms
memory: 21004kb
input:
200000 17 00100000010001001 00000000000000000 00000000000000000 00100100001000000 01010000000000001 00010000000000000 00000000000000000 00010000000000000 00000000000000000 00000000000000000 10000100000000000 00001000000000000 00000000000100000 00000000000000000 00000000000000000 00000000000010010 00...
output:
0.0594177831548869730959872015319
result:
ok found '0.059417783', expected '0.059417783', error '0.000000000'
Test #24:
score: 0
Accepted
time: 348ms
memory: 20880kb
input:
200000 17 00100000100000000 00000100001000000 00100001000000010 01010000010001011 00000000000000000 00000011010010011 10011000000000000 00000000101001000 00000000101000000 00000000010100001 00000000000000000 00000000001000100 00000000111000010 00001000000000110 01001010000000000 00000001000000000 10...
output:
0.0592168499219727501037269234985
result:
ok found '0.059216850', expected '0.059216850', error '0.000000000'
Test #25:
score: 0
Accepted
time: 339ms
memory: 21000kb
input:
200000 17 00000101010001001 00110001000001100 00001000000010001 10000100010000001 10000101000100000 10110000100100010 10010000111000000 00001000000000011 11100000000111100 10001000000010000 00101111000011010 10101000000000000 11001111000001000 00001000000010000 01000001100000111 10000001000111000 00...
output:
0.0587931899791700809942973648958
result:
ok found '0.058793190', expected '0.058793190', error '0.000000000'
Test #26:
score: 0
Accepted
time: 342ms
memory: 20832kb
input:
200000 17 00000101000101000 01010001000101001 11110110110101110 11000011010010011 11000000100101000 10100000111101001 00001110101001100 00011010110001000 01101100011000010 10000110001101011 10000001000010000 11100000100100001 01011101001000001 00001001100000111 00010001111011100 11000110000111100 00...
output:
0.0589080554881629483987559581237
result:
ok found '0.058908055', expected '0.058908055', error '0.000000000'
Test #27:
score: 0
Accepted
time: 351ms
memory: 20884kb
input:
200000 17 11011011001011010 11111101011101011 11010110101110011 00110101110010111 01011011010111010 01100011000000001 10101100111100011 01111110110100011 00110000011001111 01101010011010111 11010111110101011 01111110001110110 01110100100101111 10111000101110101 11111100111001101 00111111110101011 11...
output:
0.0588161452602882217632895844872
result:
ok found '0.058816145', expected '0.058816145', error '0.000000000'
Test #28:
score: 0
Accepted
time: 351ms
memory: 20884kb
input:
200000 17 10011011100011010 01111101101011110 11101101111111101 01111111100101101 01010101110011111 00111111111111001 01111101111110011 11111110110111010 11111010111111111 11111111111111111 11011111011101111 10111011111101011 01110001101110110 11110101110111111 11111111010111100 11011001001110111 11...
output:
0.0586305760203638531846692671934
result:
ok found '0.058630576', expected '0.058630576', error '0.000000000'
Test #29:
score: 0
Accepted
time: 338ms
memory: 20884kb
input:
200000 17 11111101111101111 11110111101111101 01111111011111111 10111111111101111 11110111111111111 11110110111010111 01110011111111111 11110110011110001 11111111001111111 01111111111111111 01111111110111111 11111111111101111 11011111111101111 01111111110110111 11111111101110101 11111111011101111 11...
output:
0.0602363448252195982091095061151
result:
ok found '0.060236345', expected '0.060236345', error '0.000000000'
Test #30:
score: 0
Accepted
time: 361ms
memory: 20880kb
input:
200000 17 11111111011111111 01111111111111111 11111111111111111 11111111111111111 11111111111111111 11111111111111111 01011111110111111 10111111111111011 11111111111111111 11111111111111101 11111111101111111 11111111111001101 11111011111111111 11111111111111110 11011111111111111 11111111111111011 11...
output:
0.057955394336645649211448017013
result:
ok found '0.057955394', expected '0.057955394', error '0.000000000'
Test #31:
score: 0
Accepted
time: 341ms
memory: 21004kb
input:
200000 17 11111111111111111 11111111111111111 11111111111111111 11111111111111111 11111101111111111 11111111111111111 11111111111111111 11111111111111111 11111111111111111 11111111111111111 11011111111111111 11111111111111111 11111110111111111 11111111111111111 11111111111111111 11111111111111111 11...
output:
0.0566815403670391931845173871807
result:
ok found '0.056681540', expected '0.056681540', error '0.000000000'
Test #32:
score: 0
Accepted
time: 348ms
memory: 20884kb
input:
200000 17 11111111111111111 11111111111111111 11110111111111111 11111111111111111 11111111111111111 11111111111111111 11111111111111111 11111111111111111 11111111111111111 11011111111111111 11111111111111111 11111111111111111 11111111111111111 11111111110111111 11111111111111111 11111111111111111 11...
output:
0.0592339090268105758485539524827
result:
ok found '0.059233909', expected '0.059233909', error '0.000000000'
Test #33:
score: 0
Accepted
time: 252ms
memory: 19860kb
input:
200000 17 11111111111111111 11111111111111111 11111111111111111 11111111111111111 11111111111111111 11111111111111111 11111111111111111 11111111111111111 11111111111111111 11111111111111111 11111111111111111 11111111111111111 11111111111111111 11111111111111111 11111111111111111 11111111111111111 11...
output:
1
result:
ok found '1.000000000', expected '1.000000000', error '0.000000000'