组合数学

https://codeforces.com/contest/1202/problem/D 题目大意 构造一个包含 $1, 3, 7$ 的字符串 $S \ (|S| \le 10^5)$ 使得其中 $1337$ 子序列的个数为 $n \ (1 \le n \le 10^9)$ 个。 简要题解 观察： 如果 $n$ 更小，我们可以直接 $133$ 然后加上 $n$ 个 $7$。或者 $1$ 是同理的。 如果用 $111333777$ 这样的结构，那么结果是 $n_1 n7 C(n3, …

https://codeforces.com/contest/1913/problem/D 题目大意 给出一个 $n \ (1 \le n \le 3 \times 10^5)$ 排列 $p$。可以做如下操作任意次： 选出一个区间 $[l, r]$ 将其中除了最小元素以外的元素全部删掉。 问结果数组共有多少种。结果对 $998244353$ 取模。 简要题解 观察： 注意到 $1$ 永远删不掉。 考虑 $2$ …

https://codeforces.com/contest/1996/problem/E 题目大意 给出 $01$ 串 $S$，长度 $\le 2 \cdot 10^5$。求其所有子串的 $01$ 个数相同的子串的个数。 简要题解 题目求 $\sum_l \sum_r \sum_x \sum_y [cnt0(x, y) == cnt1(x, y)] ,\ (1 \le l \le x \le y \le r \le n)$。 如果只有所有子串 $S(x, y)$ 的个数，那将非常好求。遇到 $0$ 就 $ …