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}\)
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}\)
本题包含三个问题：
问题 0：已知两棵 \(n\) 个节点的树的形态。要给予每个节点一个 \([1, y]\) 中的整数，使得对于任意两个节点 \(p, q\)，如果存在边 \((p, q)\) 同时属于这两棵树，则 \(p, q\) 必须被给予相同的数。求给予数的方案数。
问题 1：已知第一棵树，对于第二棵树的所有 \(n^{n−2}\) 种选择方案，求问题 0 的答案之和。
问题 2：对于第一棵树的所有 \(n^{n−2}\) 种选择方案，求问题 1 的答案之和。
对 \(998244353\) 取模
求包含 \(s\) 个叶子，非叶子节点的孩子数目在集合 \(D\) 中的有根树数量。
孩子之间有顺序，保证 \(1\notin D\)。
模质数 \(950009857=453\times 2^{21}+1\)
\(s,|D|\le 10^5\)
给定 \(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\)
有长度为 \(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\)