LOJ3123 [CTS2019] 重复

Description 给定小写字母组成的字符串 $s$ 及正整数 $m$,求有多少小写字母组成的字符串 $t$ 满足 $t$ 的无穷重复中存在一个和 $s$ 长度相同但比 $s$ 字典序小的子串。 $|s|,m\leqslant2000$。 ...

浅谈 OI 中常用的一些生成函数运算的合法与正确性

在 OI 中会用到很多生成函数运算…比如求逆(本文中均指乘法逆,而非复合逆)、$\exp$、$\ln$、牛顿迭代、微积分、拉格朗日反演等。 那么就会有很多问题,比如: ...

BZOJ5475 [WC2019] 数树

Description 对于两棵树 $T_1, T_2$,定义它们的交 $T_1\cap T_2$ 是它们的边集的交形成的森林,$k(T_1\cap T_2)$ 表示这个森林的连通块个数,求下列三种问题之一: 给定 $T_1, T_2$,求 $y^{k(T_1\cap T_2)}$; 给定 $T_1$,求 $\sum_{T_2}y^{k(T_1\cap T_2)}$; 给定 $n$,求 $\sum_{T_1}\sum_{T_2}y^{k(T_1\cap T_2)}$ 其中 $n\leqslant 10^5$,上面的 $\sum$ 都是对所有可能的 $n^{n-2}$ 种树求和。 答案对 $998244353$ 取模。 ...

BZOJ4734 [清华集训2016] 如何优雅地求和

Description 已知 $m$ 次多项式函数 $f$ 在 $0,1\dots,m$ 处的取值 $f(0),f(1),\dots,f(m)$,给定 $n,x$,求 $$\left(\sum_{k=0}^n\binom nkf(k)x^k(1-x)^{n-k}\right)\bmod998244353$$ $n\leqslant10^9,m\leqslant2\times10^4$。 ...

生成函数简介

生成函数 生成函数(generating function)又称母函数,是处理组合数学问题的一大利器。 ...

LOJ6391 [THUPC2018] Tommy神的树

Description 一棵 $n$ 个结点的树。初始时 $a$ 和 $b$ 是黑的,其他点是白的。 每次可以把某个黑点染成红的并把与它相邻的白点染成黑的。 问把结点染红的顺序有多少种。 $1\leqslant a,b\leqslant n\leqslant234567$ 答案对 $998244353$ 取模,时限 10s 。 ...

CF947E Perpetual Subtraction

Description 有一个非负整数 $x$ 。你要执行 $m$ 次操作,每次操作是 x = randint(0, x) ( = 表示赋值, randint(0, x) 均匀随机地在 $[0, x]$ 中取一个整数)。 现在已知初始的 $x$ 会随机在 $[0, n]$ 取值,且取 $i$ 的概率是 $p_i$ ,求最后取到 $[0, n]$ 每个数的概率。 $$n\leqslant10^5, m\leqslant10^{18}$$ ...

BZOJ5119 [清华集训2017] 生成树计数

Description 一个$s$个点的图,目前被$s-n$条边连成了$n$个连通块,第$i$个连通块大小为$a_i$。要求你再连$n-1$条边把它变成一棵树。对于每一棵树,若第$i$个连通块连出了$d_i$条边,其价值为 $val(T)=\left(\prod_{i=1}^nd_i^m\right)\left(\sum_{i=1}^nd_i^m\right)$ 求所有生成树的价值和$\bmod998244353$。$n \leqslant 30000, m \leqslant 30$。 ...