Bernoulli number

Codeforces 755G. PolandBall and Many Other Balls

题意

有 $n$ 个球编号为 $1,2,\dotsc,n$，一组可以是一个球 ${i}$ 或者是两个相邻的球 ${i,i+1}$

对于 $i=1,2,\dotsc,k$ 求 $n$ 个球划分成 $i$ 组的方案数，每个球至多在一个组内，并且可以不在任何一个组内

对 $998244353$ 取模

$n\le 10^9,k\le 2^{15}$

LOJ #2983. 「WC2019」数树

题意

本题包含三个问题：

• 问题 0：已知两棵 $n$ 个节点的树的形态。要给予每个节点一个 $[1, y]$ 中的整数，使得对于任意两个节点 $p, q$，如果存在边 $(p, q)$ 同时属于这两棵树，则 $p, q$ 必须被给予相同的数。求给予数的方案数。

• 问题 1：已知第一棵树，对于第二棵树的所有 $n^{n−2}$ 种选择方案，求问题 0 的答案之和。

• 问题 2：对于第一棵树的所有 $n^{n−2}$ 种选择方案，求问题 1 的答案之和。

对 $998244353$ 取模

BZOJ 3684: 大朋友和多叉树

题意

求包含 $s$ 个叶子，非叶子节点的孩子数目在集合 $D$ 中的有根树数量。

孩子之间有顺序，保证 $1\notin D$。

模质数 $950009857=453\times 2^{21}+1$

$s,|D|\le 10^5$

问题

应该是个挺简单的问题

对于 $k=0,1,\dotsc,m$ 求

$$
f_k=\sum_{i=1}^n a_i^k
$$

LOJ #6391. 「THUPC2018」淘米神的树 / Tommy

题意

有一棵 $n$ 个点的树，你要以一个顺序选择每个点恰好一次。

初始只有两个钦定点 $a,b$ 可以被选，一个点被选后所有的相邻点就可以被选择。

求方案数，模 $998244353$

特征多项式

设 $A$ 为给定的 $n\times n$ 矩阵，$I_n$ 为 $n\times n$ 单位矩阵，$A$ 的特征多项式定义为

$$
p(\lambda )=\det(\lambda I_{n}-A)
$$

其中 $\det$ 表示行列式。

Cayley–Hamilton theorem

根据 凯莱–哈密顿定理，$A$ 满足方程

$$
p(A)=0
$$

其中 $0$ 是零矩阵。

因此我们可以利用这个 $n$ 次的多项式 $p(A)$ 来降低 $A$ 的高次幂。

UOJ #269

题意

给定 $m$ 次函数 $f$ 和 $n,a$，求

$$
\sum_{k = 0}^{n}f(k)\binom{n}{k}a^k(1 - a) ^{n - k}
$$

模 $998244353$

函数给出 $0,1,\dotsc,m$ 处的点值

$1\le n\le 10^9,1\le m\le 2\times 10^4$

Luogu P4705 玩游戏

题意

有长度为 $n$ 的序列 $a$ 和长度为 $m$ 的序列 $b$

对于 $k=1,2,\dotsc,t$ 求随机两个元素 $a_i$ 和 $b_j$，$(a_i+b_j)^k$ 的期望

模 $998244353$

$n,m,t\le 10^5$

LOJ #150

题意

给定 $n$ 次多项式 $F(x)$，求 $G(x)$ 满足

$$
G(x)\equiv
\left(\left(1+\ln\left(2+F(x)-F(0)-\exp\left(\int\frac{1}{\sqrt{F(x)}}\right)\right)\right)^k\right)’ \pmod{x^n}
$$

保证常数项是模 $998244353$ 的二次剩余。

注意 $\pm\sqrt{F(x)}$ 均为合法解，你只需要输出 $\sqrt{F(x)}$，舍去 $-\sqrt{F(x)}$，我们认为两个解中常数项较小的解为 $\sqrt{F(x)}$。

所有运算在模 $998244353$ 意义下进行。