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$

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$