QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#132673#5205. Game of QuestionsSwarthmore#AC ✓361ms21004kbC++173.8kb2023-07-31 01:04:452023-07-31 01:04:48

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-31 01:04:48]
  • 评测
  • 测评结果:AC
  • 用时:361ms
  • 内存:21004kb
  • [2023-07-31 01:04:45]
  • 提交

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;
}



Details

Tip: Click on the bar to expand more detailed information

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'