danihao123's Blog

付公主有一个大小为$10^5$的背包。然你有$n$种类型的物品，其中第$i$种体积为$V_i$（是正整数），数量有$10^5$件。然后给出一正整数$m$，对任意$i=1\ldots m$求出包里恰好装了$i$体积的物品的方案数，答案对$998244353$取模。

$1\leq n\leq 10^5, m\leq 10^5, V_i\leq m$。

求$\sum_{i = 0}^n\sum_{j = 0}^i \begin{Bmatrix}i\\ j\end{Bmatrix}2^jj!$。

$1\leq n\leq 10^5$。

你有$n$个两两不同的串，你要将每个串变成其的一个前缀，使得变换后的所有串仍然两两不同，并且所有串长度和尽可能小，输出这个和。

$n\leq 10^5$，所有串长之和不超过$10^5$。

给定正整数$n, m$，求$\sum_{i = 1}^n\sum_{j = 1}^m \varphi(ij)$，膜$10^9+7$输出。

$n\leq 10^5, m\leq 10^9$。

给定$n$，分别求出$\mu(x^2)$和$\varphi(x^2)$的前$n$项和。

$1\leq n\leq 10^9$。

给定一个$2n$张卡的卡组，其中有$n$张强化卡（其权值为一大于$1$的整数），$n$张攻击卡（其权值为一正整数）。在一次游戏中，你需要有序的打出一些卡牌，如果说你打了一张权值为$x$的攻击卡，那么对对方造成$x$点伤害；如果说你打出了一张权值为$x$的强化卡，那么之后所有伤害乘上$x$。

现在，你需要随机从卡组中抽出$m$张牌，然后选出其中的$k$张照一定顺序打出，要求使得产生的伤害最大化。求伤害的期望，答案乘$\binom{2n}{m}$再膜$998244353$输出。

$1\leq k\leq m\leq 2n\leq 3000, 1\leq x\leq 10^8$（其中$x$为牌的权值）。

多组数据，满足$\sum 2n\leq 30000$。

求有多少正整数序列，满足所有数的最大公约数为$x$，所有数的和为$y$。

$1\leq x, y\leq 10^9$。

假设每个结点都有正整数权值，那么我们定义完美平衡树：权值为$1$的单点树是完美平衡树；根的权值为$w(w\geq 2)$的话，那么它一定有$k(2\leq k\leq w)$个子树，每个子树要完全一致，并且每个子树的根权值都要是$\lfloor\frac{w}{k}\rfloor$。

给定$N$，计算根权值为$N$的完美平衡树的数量。

$1\leq N\leq 10^9$。

给你一个长为$n$的整数序列$a$，求出将序列随机打乱之后的最大前缀和（不能选空前缀！）的期望，答案乘上$n!$之后对$998244353$输出。

$1\leq n\leq 20, \sum_{i = 1}^n |a_i|\leq 10^9$。

给你一棵$n$个点的树，要求你滋磁以下操作（共$m$次）：

• 对于给定的点对$(x, y)$和$(u, v)$，删除边$(x, y)$，添加边$(u, v)$。保证操作时$(u, v)$存在，并且保证操作后的图还是一棵树。
• 向集合$S$中加入一个点对$(u, v)$。
• 从$S$中删除一个点对。
• 给定一条边$(x, y)$（保证在当前树中存在），求问是否所有$(u, v)\in S$都满足$u$到$v$的路径经过了$(x, y)$。

$1\leq n\leq 10^5, 1\leq m\leq 300000$。