格路计数
stripe_python · · 算法·理论
问题 1 求
从
问题 2 求
将不合法格路碰到
可以证明,这是不合法格路的双射。得到答案
问题 3 求
直线在同侧平凡。将越过
也就是在
将终点按
mint solve(int n, int m, int b1, int b2) {
// (0, 0) -> (n, m), b1 < 0 < b2
int u = b1 - 1, v = b2 + 1;
mint res = C(n+m, n);
auto sol = [&](int st) -> void {
int x = n, y = m;
mint op = -1;
while (true) {
if (st == 0) tie(x, y) = mkpair(y-u, x+u);
else tie(x, y) = mkpair(y-v, x+v);
if (x < 0 || y < 0) break;
res += op * C(x+y, x);
st ^= 1, op = -op;
}
};
sol(0), sol(1); return res;
}
问题 4 求
不妨设
QOJ14621 Tearing Paper
定义
(0,0) \to (n,m) 的格路是合法的,当且仅当矩形[a,c] \times [b,d] 在格路同侧。求合法格路数目。多测,
T \le 10^4 ,n \le 10^3 ,m \le 10^6 ,1 秒,256 MB。
:::::success[题解]
考虑分别计数不越过射线
以
特判
对于
注意到
根据减法原理得到
必有
:::::
CF1942G Bessie and Cards
现有
a 张0 卡,b 张1 卡,c 张2 卡和5 张特殊卡。抽牌开始时,从牌顶抽取前
5 张牌,可以丢弃k 卡抽取接下来k 张牌。若抽到全部5 张特殊卡则获胜。所有卡互不相同,
(a+b+c+5)! 种牌堆等可能出现,求获胜概率。多测,
\sum a,\sum b,\sum c \le 2\times 10^5 ,2 秒,250 MB。
:::::success[题解]
抽到
可以用格路计数转化条件,抽到
枚举触碰点为坐标
限制为前
故合法方案数为
注意加上始终不碰到
除以总数
:::::
P4260 [Code+#3] 博弈论与概率统计
现有两个变量
a,b ,初始a=b=0 。进行n+m 轮操作,一轮操作中:
- 令
a \gets a+1, b \gets \max(0,b-1) 。概率为p 。- 令
a \gets \max(0,a-1), b \gets b+1 。概率为1-p 。且第一类操作恰好发生
n 次。求a 的期望。进行
q 次询问,每轮询问均给出n,m,p 并输出答案。
::::::success[题解]
容易发现
设第一类操作进行
设全过程
做一个单步容斥,即
将
至少转恰好是作差,则
-
若
n \ge m ,那么\begin{aligned} \text{ans}&=\sum_{k=0}^m (n+k-m) \left(\dbinom{n+m}{m-k}-\dbinom{n+m}{m-k-1}\right)\\ &=\sum_{i=0}^m (n-i) \left(\dbinom{n+m}{i}-\dbinom{n+m}{i-1}\right)\\ &=\sum_{i=0}^m (n-i) \dbinom{n+m}{i}-\sum_{i=0}^{m-1} (n-i-1)\dbinom{n+m}{i}\\ &=\boxed{\sum_{i=0}^{m-1} \binom{n+m}{i}+(n-m) \binom{n+m}{m}} \end{aligned} 第二步为换元
i=m-k ,第三步后面的和式i \gets i-1 ,第四步为对位相减。 -
若
n \le m ,同理化简得\begin{aligned} \text{ans}&=\sum_{k=m-n}^{m} (n+k-m) \left(\dbinom{n+m}{m-k}-\dbinom{n+m}{m-k-1}\right)\\ &=\boxed{\sum_{i=0}^{n-1} \binom{n+m}{i}} \end{aligned}
问题转化为
:::::info[组合数下指标前缀和]
模板题:AT_tenka1_2014_final_d 高橋君。
进行
q 次询问,给定n,m ,求f(n,m)=\left(\sum_{i=0}^m \binom{n}{i}\right) \bmod (10^9+7)
考察莫队思想,只要
前两条转移显然,后两条由组合数递推式裂项可得。
利用莫队构造,我们可以在
事实上这个问题也存在
:::::
::::::
P16958 [SCCPC 2026] 括号序列
给定合法括号串
S ,求有多少合法括号串T 满足|T| \le |S| 且T 的字典序不大于S 。多测,
\sum |S| \le 10^6 ,2 秒,1024 MB。
:::::success[题解]
我们将括号串转化成格路。将左括号视作
特判
在 LCP 之后
转而枚举
我们记
则
瓶颈在于
我们需要观察
0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1 10
0 0 0 0 0 0 1 9 54
0 0 0 0 0 1 8 44 209
0 0 0 0 1 7 35 155 650
0 0 0 1 6 27 111 441 1728
0 0 1 5 20 76 286 1078 4081
0 1 4 14 49 175 637 2353 8788
注意到以下等式成立:
而
维护
注意到
复杂度
:::::
P11164 [BalkanOI 2023] Permutations
给出
1\sim n 的排列p_i 。q 次询问给出l,r ,求满足下列条件的1\sim n 的排列数目:
- 排列的前缀为
p_l \sim p_r 。- 排列的 LDS 长度
\le 2 。LDS 为最长下降子序列。
:::::success[题解]
先考虑没有前缀限制怎么做,打表发现答案数列的前几项是
我们尝试将合法排列和格路计数的模型建立双射。
首先考虑从排列构造格路。我们求出前缀最大值
接着考虑从格路构造排列。先求出每个横坐标对应的高度
在这个构造中,前缀最大值和非前缀最大值构成的子序列都是递增的。由 Dilworth 定理,
现在我们强制排列的前缀为
记
用单线反射容斥来算,总方案数
原题中
设
根据区间
-
第一个条件:我们用单调栈求出
f_j=\max\limits_{i<j\land p_i >p_j} i 和g_j=\min\limits_{j < k\land p_j>p_k} k 。条件转化为\exists j \in [l,r], [f_j,g_j] \subseteq [l,r] 。这等价于
\exists i \in [l,r],l \le \min(i,f_i) \land \max(i,g_i) \le r 。由i \ge f_i, i \le g_i 可以发现i \in [l,r] 的条件没有用。因此只要判断\forall i, [f_i,g_i] \subseteq [l,r] 成立。将
(f_i,g_i) 画到二维平面上,询问变成 2-side 矩形数点,扫描线,维护x 坐标历史\max 直接判定即可。 -
第二个条件:仍用单调栈求得
f_j ,条件转化为\exists j \in [l,r], l \le f_j \land p_j>x 。我们写成\max\limits_{i \in [l,r]\land f_i \ge l} p_i>x 。将
(i,f_i) 画到二维平面上,询问是 3-side 矩形求\max ,扫描线,树状数组支持单点修改后缀\max 即可。
视
:::::