THC

WIKI

0%

gym101385Problem A. Number of Close Strings

Posted on

简要题意

有 \(k\) 个长度为 \(n\) 的 \(01\) 串，和一个正整数 \(m\) 。求有多少个长度为 \(n\) 的 \(01\) 串，满足和至少一个给出的 \(01\) 串最多 \(m\) 位不同。满足相对误差在 \(\varepsilon=10^{-2}\) 内即可。

数据范围 \(1\le n,k\le 50, 1\le m\le n\) ，时限 \(10s\) 。

前置结论

一个随机采样的问题，有结论：

定理 1

有一个随机数生成器，返回的数字在 \([A,B]\) 之间，期望为 \(E_0\) ，方差为 \(\sigma^2\) 。那么随机 \(N\) 次，求出返回数的平均值，该平均值与 \(E_0\) 的绝对误差期望为 \(O(\sigma N^{-\frac12})\) 。

证明.

设随机 \(N\) 次的返回结果为 \(a_1,a_2,\cdots,a_N\) ，平均值即为 \(\frac{a_1+a_2+\cdot+a_N}{N}\) 。

先求 \(E((\frac{a_1+a_2+\cdot+a_N}{N}-E_0)^2)\) 的值。

\[ \begin{gather*} E\left((\frac{a_1+a_2+\cdot+a_N}{N}-E_0)^2\right)=\frac{1}{N^2}E\left(\left(\sum_{i=1}^N(a_i-E_0)\right)^2\right)\\ =\frac{1}{N^2}\left(\sum_{i=1}^NE\left((a_i-E_0)^2\right)+\sum_{1\le i<j\le N}2E(a_i-E_0)E(a_j-E_0)\right)\\ =\frac{1}{N^2}\cdot N\cdot\sigma^2=\frac{\sigma^2}{N} \end{gather*} \]

所以绝对误差期望为 \(O(\sigma^2N^{-1})\) 。

定理 2

有一个随机数生成器，返回的数字在 \([A,B]\) 之间，期望为 \(E_0\) ，方差为 \(\sigma^2\) 。那么随机 \(N\) 次，求出返回数的平均值，设该数与 \(E_0\) 的绝对误差为 \(\delta\) ，那么几乎一定有 \(\delta<O(\sigma N^{-\frac12})\) 。

证明.

设绝对误差为 \(\delta=|\frac{a_1+a_2+\cdot+a_N}{N}-E_0|\) 。考虑对于任意常数 \(c\) ，求出

\[ Pr(\delta>c\cdot \sigma N^{-\frac12}) \]

由 \(\text{Hoeffding's inequality}\) ，

\[ \begin{gather*} Pr(\delta N>c\cdot \sigma N^{\frac12})\\ \le 2\exp\left(-\frac{2(c-1)^2\sigma^2N}{N(B-A)^2}\right)\\ =2\exp\left(-2(c-1)^2\cdot\frac{\sigma^2}{(B-A)^2}\right) \end{gather*} \]

注意到该式与 \(N\) 无关且随着 \(c\) 增大而指数级减小，故得证。

该定理告诉我们，如果要求出 \(E_0\) 的近似值，满足绝对误差不超过 \(\varepsilon\) ，则只需让 \(N=\Theta(\sigma^2\varepsilon^{-2})\) 即可。

进一步地，为使用方便，给出一下直接结论：

引理 2

有一个随机数生成器，返回的数字在 \([A,B]\) 之间，期望为 \(E_0\) 。那么随机 \(N\) 次，求出返回数的平均值，设与 \(E_0\) 的绝对误差为 \(\delta\) 那么几乎一定有 \(\delta<O\left((B-A)N^{-\frac12}\right)\) 。

证明.

由于 \(\sigma\le B-A\) ，该式显然成立。

题解

有了以上结论后，我们就可以解决这道题。

设 \(S_i\) 为和第 \(i\) 个串至多 \(m\) 位不同的 \(01\) 串集合，设 \(S=S_1\bigcup\cdots\bigcup S_k\) ，所求即为 \(|S|\) 。显然有 \(|S_1|=|S_2|=\cdots=|S_k|\) ，设为 \(M\) ，显然 \(M=\sum\limits_{i=0}^{m}\binom{n}{i}\) 。

设 \(S=\{a_1,a_2,\cdots,a_{|S|}\}\) ， \(b_i\) 为 \(a_i\) 在 \(S_1,S_2,\cdots,S_k\) 中出现次数。设 \(S_r=\{a_{r_1},a_{r_2},\cdots,a_{r_M}\}(1\le r\le |S|)\) 。构造一个序列 \(x_1,x_2,\cdots,x_{kM}\) ，其中 \(x_{(r-1)M+s}=\dfrac{1}{b_{r_s}}(1\le r\le k,1\le s\le M)\) 。

于是显然有 \(|S|=\sum\limits_{i=1}^{kM}x_i\) ，即为想要求出的值。但 \(kM\) 过大无法直接计算，又由于 \(kM\) 已知，我们只需要估计 \(E(x_i)\) 的值就可以求出答案的近似值。等概率随机 \(x_i\) 是容易的，考虑随机采样 \(N\) 次，由引理2，绝对误差以极大概率不超过 \(O(N^{-\frac12})\) ，又因为所求平均值在 \([\dfrac{1}{k},1]\) 中，故相对误差不超过 \(O(kN^{-\frac12})\) ，取 \(N=\Theta(k^2\sigma^{-2})\) 即可。

在实现中使用 \(\text{popcount}\) 统计不同位数，每次随机出一个 \(x_i\) 后就可以做到 \(O(k)\) 统计，于是总时间复杂度为 \(O(Nk)=O(k^3\sigma^{-2})\) 可以通过本题。在实现中，可以不严格 \(N=\Theta(k^2\sigma^{-2})\) 而采用运行时间来决定采样次数，本题时限 \(10s\) 可采样 \(9s\) ，实测可通过此题。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define Mp make_pair
#define pb push_back
#define SZ(a) (int(a.size()))

typedef long long ll;
typedef double db;
typedef pair<int, int> pii;
typedef vector<int> vi;
#define debug(...) fprintf(stderr, __VA_ARGS__)
mt19937_64 gen(std::chrono::system_clock::now().time_since_epoch().count());
ll get(ll l, ll r) { uniform_int_distribution<ll> dist(l, r); return dist(gen); }

int n, k, m, p[100]; ll a[100], c[100][100], M, N; char s[100];
ll getnum() {
    ll t = 0;
    while((1ll << t) <= M) t++;
    ll q;
    while(1) {
        q = get(0, (1ll << t) - 1);
        if(q < M) break;
    }
    for(int i = 0; i <= m; i++) {
        if(q < c[n][i]) {
            int s = i;
            ll res = 0;
            for(int j = n; j; j--) {
                res <<= 1;
                if(get(0, j - 1) < s)
                    res++, s--;
            }
            assert(s == 0);
            return res;
        } else q -= c[n][i];
    }
}
signed main() {
    db ti = clock();

    freopen("close.in", "r", stdin);
    freopen("close.out", "w", stdout);

    scanf("%d %d %d", &n, &k, &m); m--;
    iota(p + 1, p + 1 + n, 1);
    for(int i = 1; i <= k; i++) {
        scanf("%s", s + 1);
        for(int j = 1; j <= n; j++)
            a[i] = a[i] * 2 + s[j] - '0';
    }
    db sum = 0;
    for(int i = 0; i <= n; i++) {
        c[i][0] = c[i][i] = 1;
        for(int j = 1; j < i; j++)
            c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
    }
    for(int i = 0; i <= m; i++) M += c[n][i];
    // debug("M = %lld\n", M);
    // debug("N = %lld\n", N);
    while((clock() - ti) <= 9 * CLOCKS_PER_SEC) {
        ll num = getnum() ^ a[get(1, k)];
        int b = 0;
        for(int i = 1; i <= k; i++) {
            if(__builtin_popcountll(num ^ a[i]) <= m)
                b++;
        }
        assert(b);
        N++, sum += 1. / b;
    }
    sum = sum / N * k * M;
    printf("%.10lf\n", sum);
    debug("time=%.4lfs\n", (db)clock()/CLOCKS_PER_SEC);
    return 0;
}

参考资料

国家集训队2022论文集-浅谈OI中的近似算法-许庭强