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\)。