E - Paper Cutting 2¶

题意¶

$H\times W$ のマス目に区切られた長方形の紙があり、このうちちょうど $2$ マスが黒く、残りの部分は白く塗られています。マス目の $i$ 行目、 $j$ 列目にあるマスを $(i,j)$ で表すと、黒く塗られているのはマス $(h_1,w_1)$ とマス $(h_2,w_2)$ です。

maroon 君はこれから以下の手順で紙を切断する操作を繰り返します。

現在の紙のマス目が $h\times w$ の時、紙の辺に平行でマスの境界を通るような直線には、 $(h−1)$ 本の横線と $(w−1)$ 本の縦線がある。この中から $1$ 本を一様ランダムに選んで、その直線に沿って紙を $2$ 枚に切断する。このとき、
- $2$ つの黒いマスが同じ紙に存在するとき、もう片方の紙を捨て、操作を続ける
- そうでなければ、操作を終了する

maroon 君が操作を終了するまでに紙を切断する回数の期待値を $\bmod 998244353$ で求めてください。

解析¶

将 $H+W-2$ 条切割线编号。对于一个 $1$ 至 $H+W$ 的排列 $p$ ，我们这样建立它与操作序列的联系：依次切割 $p_i$ 对应的切割线，若对应切割线已经不存在则忽略，若切割成两片带黑块的纸则终止。

则每一个 $1$ 至 $H+W-2$ 的排列都对应一个合法的操作序列，每一个合法的操作序列都对应若干个排列。且每个操作序列对应的排列数占比等于它出现的概率(※)。

我们称能够将纸分为两份都带有黑块的切割线为内切割线 (不妨设有 $n$ 条)，其余的按其位置分为上、下、左、右切割线。对于上切割线，我们按其距内切割线的距离从近到远编号为 $1,2,\ldots,m$ ，则第 $i$ 条线只有在排列中的位置位于 $1,2,\ldots,i-1$ 和所有内切割线之前时才会被切割，则其被切割的概率 (同时也是其对答案的贡献) 为 $\dfrac{1}{i+n}$ 。对下左右如法炮制即可。

预处理阶乘可以做到线性复杂度。

(※)抽象地说，用一个范围为 $[L,R]$ 的均匀随机数生成器生成 $[l,r]$ ( $L\le l\le r\le R$ ) 范围的随机数 (若超出范围，重新生成，直到结果在范围内)，结果还是均匀的。舍去部分不影响保留部分的概率分布。具体地说，对于一个排列的前缀 $p[1\ldots i]$ ，其中已切割的一些切割线会导致后面的某些切割线被忽略。然而，这些被忽略的切割线 (数量记做 $m$ ) 会使后面每种可能的操作序列对应的排列数均等地乘上 $\binom{n-i}{m}m!$ ，不影响相对概率。因此，每一个前缀对应的所有排列的相对概率都没有被影响。

实现¶

#include <bits/stdc++.h>

typedef long long int ll;
const int maxn = 2e5 + 19, mod = 998244353;

void exgcd(int a, int b, int &x, int &y){
    if(!b) return (void)(x = 1, y = 0);
    exgcd(b, a % b, y, x), y -= a / b * x;
}

int fact[maxn], ifact[maxn];
void init(int n){
    fact[0] = 1;
    for(int i = 1; i <= n; ++i) fact[i] = (ll)fact[i - 1] * i % mod;
    exgcd(fact[n], mod, ifact[n], ifact[0]), ifact[n] = (ifact[n] % mod + mod) % mod;
    for(int i = n - 1; i >= 0; --i) ifact[i] = (ll)ifact[i + 1] * (i + 1) % mod;
}

inline int inv(int n){
    return (ll)ifact[n] * fact[n - 1] % mod;
}

int H, W, h[2], w[2];
int dp[maxn], ans;

int solve(int a, int b){
    int res = 0;
    for(int i = 1; i <= a; ++i)
        res = (res + inv(i + b)) % mod;
    return res;
}

int main(){
    std::scanf("%d%d%d%d%d%d", &H, &W, h, w, h + 1, w + 1);
    if(h[0] > h[1]) std::swap(h[0], h[1]);
    if(w[0] > w[1]) std::swap(w[0], w[1]);
    init(H + W);
    int n = h[1] - h[0] + w[1] - w[0];
    ans = (
    1ll +
    solve(h[0] - 1, n) +
    solve(H - h[1], n) + 
    solve(w[0] - 1, n) +
    solve(W - w[1], n)
    ) % mod;
    std::printf("%d\n", ans);
}

来源¶

AtCoder Regular Contest 114 E - Paper Cutting 2

E - Paper Cutting 2¶

题意¶

解析¶

实现¶

来源¶

评论