2022 ICPC Asia EC 网络赛第一场 J 题题解

题目来源: 2022 ICPC Asia EC 网络赛第一场: J. Gachapon

比赛链接: https://pintia.cn/market/item/1571156622976593920

题面

考虑抽卡操作: 若第 \(1\) 次操作至第 \(i-1\) 次操作都为操作失败, 则第 \(i\) 次操作成功的概率为 \(p_i\), 成功后停止操作, 否则进行第 \(i+1\) 次操作. 现给定正整数 \(X,Y\), 构造数列 \(\{p_i\}\) 满足下述条件:

第 \(X\) 次操作一定成功. 即 \(p_X=1\).
第 \(1\) 次至第 \(X-1\) 次操作都不能保证一定成功. 即 \(\forall i\in[1,X), p_i<1\).
任何操作都不能不可能成功. 即 \(\forall i, p_i>0\).
期望上是第 \(Y\) 次抽卡成功.

数据范围

\[ 1<Y<X\le100 \]

输出格式

\(\forall i\), \(p_i\) 需为 \([0,1]\) 中的有理数. 设 \(p_i=a_i/b_i\), 其中 \(a_i,b_i\) 为正整数且 \(\gcd(a_i,b_i)=1\), 则 \(a_i,b_i\) 需满足: \[ 0\le a_i,b_i\le10^4 \] 输出 \((a_i,b_i)\) 表示 \(p_i\).

题解

由题意, 在第 \(i\) 次成功的概率为 \[ P_i=p_i\prod_{k=1}^{i-1}(1-p_k) \]

记期望上的抽卡成功次数为 \(E\), 由数学期望的定义可知 \[ E=\sum_{i}iP_i \] 现记 \(q_i:=1-p_i\), \[ Q_i:=\prod_{k=1}^{i-1}q_k=\prod_{k=1}^{i-1}(1-p_k) \]

若读者没有耐心阅读下段证明, 可以直接从这里跳至 (1) 式.

则有: \[ E=\sum_iiP_i=\sum_iip_iQ_i=\sum_i\sum_{s=1}^ip_iQ_i=\sum_s\sum_{i\ge s}p_iQ_i \] 记 \[ I_s:=\sum_{i=s}^\infty p_i\prod_{j=s}^{i-1}q_j=\sum_{i=s}^\infty p_i\frac{Q_i}{Q_s}=\frac1{Q_s}\sum_{i=s}^\infty p_iQ_i \] 则有: \[ E=\sum_s\sum_{i\ge s}p_iQ_i=\sum_sQ_sI_s \] 由于 \(I_s\) 是级数, 记其前 \(t\) 项和为 \[ \begin{aligned} I_{s,t}:=\sum_{i=s}^tp_i\prod_{j=s}^{i-1}q_j &=\sum_{i=s}^tp_i\prod_{j=s}^{i-1}q_j+\prod_{j=s}^tq_j-\prod_{j=s}^tq_j \end{aligned} \] 由于对于任意 \(k\ge s\), 都有 \[ \begin{aligned} J_{s,k}:=&\sum_{i=s}^kp_i\prod_{j=s}^{i-1}q_j+\prod_{j=s}^kq_j\\ =&\sum_{i=s}^{k-1}p_i\prod_{j=s}^{i-1}q_j+p_k\prod_{j=s}^{k-1}q_j+q_k\prod_{j=s}^{k-1}q_j\\ =&\sum_{i=s}^{k-1}p_i\prod_{j=s}^{i-1}q_j+(p_k+q_k)\prod_{j=s}^{k-1}q_j\\ =&\sum_{i=s}^{k-1}p_i\prod_{j=s}^{i-1}q_j+\prod_{j=s}^{k-1}q_j=J_{s,k-1} \end{aligned} \] 故 \(J_{s,t}=J_{s,s}=1\). 则 \[ \begin{aligned} I_{s,t}=\sum_{i=s}^tp_i\prod_{j=s}^{i-1}q_j+\prod_{j=s}^tq_j-\prod_{j=s}^tq_j=J_{s,t}-\prod_{j=s}^tq_j=1-\frac{Q_{t+1}}{Q_s} \end{aligned} \] 故 \[ \newcommand{\brac}[1]{\left( #1 \right)} \newcommand{\abs}[1]{\left| #1 \right|} I_s=\lim_{t\rightarrow\infty}I_{s,t}=\lim_{t\rightarrow\infty}\brac{1-\frac{Q_{t+1}}{Q_s}}=1-\frac{Q_\infty}{Q_s} \] 若 \(Q_\infty=0\), 则 \(I_s=1\). 一般情况下, 即使 \(Q_\infty\) 中连乘中的各项 \(q_i\) 都有 \(0< q_i\le1\), 也不能保证 \(Q_\infty=0\), 因为 \[ Q_\infty=\exp\brac{-\sum\abs{\ln q_i}} \] 而通过巧妙的构造可以使 \(\sum\abs{\ln q_i}\) 收敛, 从而 \(Q_\infty>0\).

然而, 由限制条件 1 可知 \(p_X=1\) 从而 \(q_X=0\), 故 \(\forall n>X, Q_n=0\), 从而 \(Q_\infty=0\). 故 \(I_s=1\).

故本题有重要结论: \[ E=\sum_sQ_s\tag1 \] 关于该结论, 比较直观的理解为: \(Q_s\) 为需要执行第 \(s\) 次抽卡操作的概率, 而无论该次抽卡操作结果如何, 都是进行了 \(1\) 次操作, 其都会对期望恰好产生 \(1\) 次的贡献. 上述推导中求和号的交换顺序可以视为该思想的体现.

现只需构造 \(\{Q_i\}\) 使 \(E=Y\) 即可. 由于 \[ p_i=1-q_i=1-\frac{Q_{i+1}}{Q_i} \] 故构造完成 \(\{Q_i\}\) 后可以直接得到 \(\{p_i\}\).

现给出一种构造方案: 令 \(Q_i=x_i/C\), 其中 \(x_i,C\) 为整数, 但不一定有 \(\gcd(x_i,C)=1\). 则 \(\forall i>X\), \(x_i=0\). 由于 \(\forall i\in[1,X)\), \(p_i<1\), \(q_i>0\), 故 \(\forall i\in(1,X]\), \(Q_i>0\), \(x_i>0\). 由于 \(Q_1=1\), 故 \(x_1=C\). 根据 \((1)\) 式有 \[ \sum_ix_i=C\sum_iQ_i=CY\tag2 \] 且 \[ p_i=1-\frac{Q_{i+1}}{Q_i}=1-\frac{x_{i+1}}{x_i}=\frac{x_i-x_{i+1}}{x_i}\tag3 \] \(\forall i\in[1,X)\), 由于 \(0<p_i<1\), 故有 \(x_i>x_{i+1}\). 即: \[ C=x_1>x_2>x_3>\cdots>x_X>0=x_{X+1}\tag4 \]

考虑 \(C\) 的选取: 考虑 \(CY\) 的上界 \[ CY=\sum_{i=1}^X x_i\le\sum_{i=1}^X(C-i+1)=\frac12{X(2C+1-X)} \] 求解可得 \[ C\ge\frac{X^2-X}{2(X-Y)}\tag5 \] 再考虑 \(CY\) 的下界 \[ CY=\sum_{i=1}^Xx_i\ge C+\sum_{i=2}^X(X-i+1)=C+\frac12X(X-1) \] 求解可得 \[ C\ge\frac{X^2-X}{2(Y-1)}\tag6 \] 现考虑输出格式带来的范围: 对于 \(C\), 我们希望 \(C\) 在满足 \((5)(6)\) 式的同时还能满足 \(C\le 10^4\). 由于 \(X\le100\), \(X-Y\ge1\), \(Y-1\ge1\), 故不等式右侧有 \[ \frac{X^2-X}{2(X-Y)}\le\frac{100^2-100}2=4950 \] \[ \frac{X^2-X}{2(Y-1)}\le\frac{100^2-100}2=4950 \]

故无论何种情况, 均能选取一个 \(C\) 在满足 \((5)(6)\) 式的同时还能满足 \(C\le 10^4\), 例如取 \(C=10^4\).

由于 \(x_i\le C\). 故 \(x_i-x_{i+1}\le x_i\le C\), 而最终 \(a_i, b_i\) 的构造结果为: \[ g_i=\gcd(x_i-x_{i+1},x_i) \]

\[ a_i=\frac{x_i-x_{i+1}}{g_i}\le x_i-x_{i+1}\le C\le10^4 \]

\[ b_i=\frac{x_i}{g_i}\le x_i\le C\le10^4 \]

构造结果满足所有题设.

代码实现

#include <bits/stdc++.h>
using namespace std;

int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}

int main()
{
    int x, y;
    cin >> x >> y;
    const int n = 10000;
    vector<int> uq(x);
    uq[0] = n;
    int sum = n;
    for (int i = 1; i < x; ++i)
    {
        uq[i] = x - i;
        sum += uq[i];
    }
    int target = n * y;
    for (int i = 1; i < x; ++i)
    {
        int maxuq = uq[i - 1] - 1;
        int maxadd = maxuq - uq[i];
        int taradd = target - sum;
        if (taradd > maxadd)
        {
            uq[i] = maxuq;
            sum += maxadd;
        }
        else
        {
            uq[i] += taradd;
            sum += taradd;
            break;
        }
    }
    for (int i = 0; i < x - 1; ++i)
    {
        int up = uq[i + 1];
        int dp = uq[i];
        up = dp - up;
        int gp = gcd(up, dp);
        up /= gp;
        dp /= gp;
        cout << up << " " << dp << "\n";
    }
    cout << "1 1";
    return 0;
}