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\)
应该是个挺简单的问题
对于 \(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\) 表示行列式。
根据 凯莱–哈密顿定理，\(A\) 满足方程
\[ p(A)=0 \]
其中 \(0\) 是零矩阵。
因此我们可以利用这个 \(n\) 次的多项式 \(p(A)\) 来降低 \(A\) 的高次幂。
给定 \(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\)
给定 \(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\) 意义下进行。