Project Euler 316

发表于 分类于 阅读次数： 本文字数： 3.5k 阅读时长 ≈ 3 分钟

Project Euler 316

题目

Numbers in decimal expansions

Let \(p=p_1p_2p_3\dots\) be an infinite sequence of random digits, selected from \(\{0,1,2,3,4,5,6,7,8,9\}\) with equal probability.

It can be seen that \(p\) corresponds to the real number \(0.p_1p_2p_3\dots\)

It can also be seen that choosing a random real number from the interval \([0,1)\) is equivalent to choosing an infinite sequence of random digits selected from \(\{0,1,2,3,4,5,6,7,8,9\}\) with equal probability.

For any positive integer \(n\) with \(d\) decimal digits, let \(k\) be the smallest index such that

\(p_k, p_{k+1}, \dots p_{k+d-1}\) are the decimal digits of \(n\), in the same order.

Also, let \(g(n)\) be the expected value of \(k\); it can be proven that \(g(n)\) is always finite and, interestingly, always an integer number.

For example, if \(n = 535\), then

for \(p = 31415926\mathbf{535}897\dots\), we get \(k = 9\)

for \(p = 35528714365004956000049084876408468\mathbf{535}4\dots\), we get \(k = 36\)

etc and we find that \(g(535) = 1008\).

Given that \(\sum \limits_{n = 2}^{999} {g \left ( \left \lfloor \dfrac{10^6}{n} \right \rfloor \right )} = 27280188\), find \(\sum \limits_{n = 2}^{999999} {g \left ( \left \lfloor \dfrac{10^{16}}{n} \right \rfloor \right )}\).

Note: \(\lfloor x \rfloor\) represents the floor function.

解决方案

鞅是什么

在概率论里，鞅（martingale）就是一种“在已知过去的情况下，对未来的期望不变”的随机过程。直觉上它刻画的是“公平游戏”：你现在手里的期望财富，不会因为你知道了过去发生了什么而改变。

更正式一点：

  • 设 \((X_t)_{t\ge 0}\) 是一列随机变量（离散时间）。
  • 设 \(\mathcal F_t\) 表示“到时间 \(t\) 为止你能知道的所有信息”（称为过滤/信息流）。

那么 \((X_t)\) 是一个鞅，意思是满足：

  1. \(X_t\) 可积：\(\mathbb E[|X_t|]<\infty\)；
  2. \(X_t\) 只依赖于到 \(t\) 的信息：\(X_t\) 对 \(\mathcal F_t\) 可测（可理解为“时刻 \(t\) 你确实知道 \(X_t\)”）；
  3. 关键条件（鞅条件）：\(\mathbb E[X_{t+1}\mid \mathcal F_t]=X_t.\)这句话读作：在已知过去所有信息 \(\mathcal F_t\) 的前提下，下一时刻的期望值等于当前值。

定义首次出现完成位置（匹配末位下标）为\(\tau=\min\{t\ge n:\ (p_{t-n+1},\dots,p_t)=(s_1,\dots,s_n)\}.\)

题目里要的起始下标是\(k=\tau-n+1,\)

因此\(g(s)=\mathbb E[k]=\mathbb E[\tau]-n+1.\)

我们构造一个“赌场 + 赌徒”模型，把“等待出现 \(s\)”转化为一个可停止的鞅，从而算出期望。

在时刻 \(i=1,2,3,\dots\)，都有一个新赌徒 \(G_i\) 进场，初始资金为 \(1\)。赌徒 \(G_i\) 从 \(p_i\) 开始尝试“押中”串 \(s\)：

  • 第 \(1\) 步押 \(p_i=s_1\)；
  • 第 \(2\) 步押 \(p_{i+1}=s_2\)；
  • …
  • 第 \(n\) 步押 \(p_{i+n-1}=s_n\)。

规则：每一步赌徒都押上全部当前资金，若押中，则资金乘以 \(10\)；若押错，则资金变为 \(0\) 并永久出局；若连续押中 \(n\) 步，则资金变为 \(10^n\) 并领奖退出。

设某赌徒某一步押之前资金为 \(C\)，则押完这一步后的资金满足 \[ \mathbb E[C_{\text{new}}\mid C] =\frac1{10}\cdot(10C)+\frac9{10}\cdot 0 =C. \] 所以单个赌徒的资金过程是鞅。

令 \(M_t\) 表示在读完第 \(t\) 个数字后（并结算完第 \(t\) 轮赌注后），场上所有赌徒资金之和。

  • 每一轮会新增一个赌徒，带来 \(+1\) 的资金投入；
  • 结算（乘 \(10\) 或变 \(0\)）对期望不改变（鞅性质）。可以认为，只要赌徒无论是胜利还是输了被迫退出，他的财富是不会变的。

因此整体上有\(\mathbb E[M_t]=t.\)

现在我们在停止时刻 \(\tau\) 停下（也就是第一次出现 \(s\) 的完成位置）。由于每个赌徒资金都被 \(10^n\) 上界束缚，因此\(M_t\le 10^n\cdot t\)。

令\(Y_t=M_t-t\)，因为每一步新进来一个赌徒使总资金多 \(1\)，下注结算是公平的，因此有\(\mathbb E[Y_{t+1}\mid \mathcal F_t]=Y_t\)，即 \((Y_t)\) 是鞅。可见，由于\(M_t\)是有界的，因此\(Y_t\)也是有界的。因此根据可停止鞅的标准条件可以得到\(\mathbb E[Y_\tau]=\mathbb E[Y_{0}]\)。这里\(Y_0=0\)，因此\(\mathbb E[M_{\tau}-\tau]=0\)，从而有\(\mathbb E[M_{\tau}]=\mathbb E[\tau]\)。

到时刻 \(\tau\)，最后 \(n\) 个数字正好是 \(s:(p_{\tau-n+1},\dots,p_\tau)=(s_1,\dots,s_n).\)

考虑那些可能还未退出的赌徒：对任意 \(k\in\{1,2,\dots,n\}\)，看赌徒 \(G_{\tau-k+1}\)。他从位置 \(\tau-k+1\) 开始，恰好经历了 \(k\) 步下注，对应检查的是最后 \(k\) 位：\((p_{\tau-k+1},\dots,p_\tau)=(s_1,\dots,s_k).\) 但左边其实就是 \(s\) 的后缀长度 \(k\)：\((p_{\tau-k+1},\dots,p_\tau)=(s_{n-k+1},\dots,s_n).\)

因此赌徒 \(G_{\tau-k+1}\) 在 \(\tau\) 时刻存活当且仅当\((s_1,\dots,s_k)=(s_{n-k+1},\dots,s_n),\)也就是当且仅当 \(k\in U\)。

而一旦存活了 \(k\) 步，他的资金就是 \(10^k\)。于是\(\displaystyle{M_\tau=\sum_{\substack{k\in U\\k\ge 1}}10^k.}\)

这是一个只由模式 \(s\) 决定的确定值（不依赖随机序列的具体结果）。

结合上一节的 \(\mathbb E[M_\tau]=\mathbb E[\tau]\)，立刻得到\(\displaystyle{\mathbb E[\tau]=\sum_{\substack{k\in U\\k\ge 1}}10^k.}\)

最后回到题目要的 \(k=\tau-n+1\)：\(\displaystyle{\mathbb E[k]=\mathbb E[\tau]-n+1=\sum_{\substack{k\in U\\k\ge 1}}10^k-n+1.}\)

如果把 \(0\) 也放进 \(U\)（它永远在），则多了 \(10^0=1\)，于是有最终答案：

\[ g(s)=\sum_{k\in U}10^k-n. \]

为了在线性复杂度以内完成\(g(s)\)的计算，使用KMP算法将集合\(U\)计算出来。

代码

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 16;
const int M = 999999;

ll pw10[N + 4];
int nxt[N + 4];
ll solve(char *s)
{
    int n = strlen(s + 1);
    ll ans = -n;
    for (int i = 2, j = 0; i <= n; i++)
    {
        while (j && s[j + 1] != s[i])
            j = nxt[j];
        if (s[j + 1] == s[i])
            ++j;
        nxt[i] = j;
    }
    for (int i = n; i; i = nxt[i])
        ans += pw10[i];
    ans += pw10[0];
    return ans;
}
int main()
{
    char s[N + 4];
    pw10[0] = 1;
    for (int i = 1; i <= N + 1; i++)
        pw10[i] = pw10[i - 1] * 10;
    ll ans = 0;
    for (int i = 2; i <= M; i++)
    {
        int n = sprintf(s + 1, "%lld", pw10[N] / i);
        ans += solve(s);
    }
    printf("%lld\n", ans);
}