The 1st Universal Cup. Stage 5: Osijek¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 4 | 5 | 10 |
A¶
**solved/upsolved by **
题意¶
题解¶
B¶
**solved/upsolved by **
题意¶
题解¶
C¶
**solved/upsolved by **
题意¶
题解¶
D¶
upsolved by TYB
题意¶
求长度为 \(n\) 的 01 串有多少个本质不同的长度为 \(k\) 的子序列。
\(1\le k\le n\le 2\times 10^5\)
题解¶
朴素的 dp：\(f[i][j]\) 表示到第 \(i\) 位长度为 \(j\) 的方案数，但转移需要用到下一个 0/1 的位置，无法优化。
考虑换一种方式 dp：\(f[i][j][0/1]\) 表示到第 \(i\) 位，长度为 \(j\)，最后一位为 0/1 的方案数，以下一位是 0 为例，转移如下： $$ f[i][j][0]=f[i-1][j-1][0]+f[i-1][j-1][1]+(j==1) $$
\[
f[i][j][1]=f[i-1][j][1]
\]
可以用分治 NTT 优化。
E¶
**solved/upsolved by **
题意¶
题解¶
F¶
**solved/upsolved by **
题意¶
题解¶
G¶
**solved/upsolved by **
题意¶
题解¶
H¶
**solved/upsolved by **
题意¶
题解¶
I¶
solved by TYB
题意¶
签到。
题解¶
略。
J¶
**solved/upsolved by **
题意¶
题解¶
K¶
**solved/upsolved by **
题意¶
题解¶
L¶
**solved/upsolved by **