A Remove a Progression

B Yet Another Crosses Problem

C From S To T

D 1-2-K Game

两个人游戏，从 $n$ 数到 $0$，每次选择 $-1,-2,-k$ 三种中一个，无法操作者为负，判断是否先手必胜。

必胜态 / 必败态打表观察。

E Count The Rectangles

给了一堆水平线和竖直线，求能够拼成多少个矩形。

枚举右边界，扣出与右边界相交的横线，枚举左边界，从左到右扫描线，树状数组维护横线的纵坐标出现位置。

时间复杂度 $\mathcal{O}(n^2 \log n)$。

F Crossword Expert

总时间为 $T$，依次发生 $n$ 个事件，每个事件时长为 $t_i$，每个事件的时长各有一半的概率不变和变成 $t_i+1$，求发生事件次数的期望。

设发生事件 $i$ 至少需要时间 $pre$，即前缀和，最多花费时间 $pre+i$，那么事件 $i$ 发生的概率为 $\sum_{j=0}^{T-pre}{ i \choose j } / 2^i$。

因此题意变成求一堆这样的组合数，分治 NTT 莫队即可。

$n$ 个点 $n$ 条边的联通图是一棵基环树，边由 $n-1$ 条树边加上一条环边组成。

Trick

• 拆出一条环边，剩余当成树做。

• 抠出整个环，环上每个点挂了一棵子树，先做 Tree dp，在环上做序列 dp。