给出 $T$ 组询问，每组用 $n, a, b, c, k_1, k_2$ 来描述。对于每组询问，请你求出

$$
\sum_{x = 0} ^ {n} x ^ {k_1} {\left \lfloor \frac{ax + b}{c} \right \rfloor} ^ {k_2}
$$

对 $1000000007$ 取模。

有 $n$ 个集合，初始都为空，要求支持：

1. 向第 $[l, r]$ 个集合中加入 $x$。
2. 求第 $i$ 个集合的元素个数。

每次向平面中添加一个点 $P$，求当前点集的直径（任意两点最大距离）的平方。
数据随机

给一棵树，随机选取两个点，求两点间路径距离为质数的概率。

有一张 $n$ 个节点的有向无环图，节点编号为 $1 \sim n$。图的连边情况如下：

• $\forall 1 \leq i \leq n - 1$，存在一条节点 $i$ 连向节点 $i + 1$ 的边，权值为 $a_i$。
• $\forall 1 \leq i \leq n - 2$，存在一条节点 $i$ 连向节点 $i + 2$ 的边，权值为 $b_i$。
• $\forall 1 \leq i \leq n - 3$，存在一条节点 $i$ 连向节点 $i + 3$ 的边，权值为 $c_i$。

除此之外，图中不存在其它的边。
对于一对节点 $s$ 和 $t$ $(s \lt t)$，记 $d(s, t)$ 为从 $s$ 到 $t$ 的最短路径长度。请你求出所有的 $d(s, t)$ 之和，其中 $1 \leq s \lt t \leq n$。

优化 NTT 的速度。

给出一个数列 $a_i$，有 $q$ 个询问 $(l, r, k)$，每次询问区间 $[l, r]$ 中的数从小到大排序且去重后第 $k$ 大的数，强制在线。

有 $N$ 座山排成一排，每座山都有一个 $1 \sim N$ 的唯一编号。第 $i$ 座山的编号为 $P_i$，高度为 $H_i$。
大厨从第一座山出发，目标是到达第 $N$ 座山。他可以从第 $i$ 座山跳到第 $j$ 座山上（$i < j, P_i < P_j$），并花费 $(H_i - H_j) ^ 2$ 的能量，当大厨处于第 $i$ 座山时，他还会花费 $A_i$ 的能量（$A_i$ 可以为负）。

求最小能量花费。

求第 $n$ 个含有大于 $1$ 的平方因子的数。

给出一个无向连通图，求所有点对的最小割数值中不同的个数。

一些模板。

给出一个 $n$ 个节点的树，和一个长为 $n$ 的排列 $p$，要求支持：

1. 求 $\sum\limits_{i = l} ^ r \mathrm{dis}(p_i, x)$
2. $\mathrm{swap}(p_i, p_{i + 1})$

强制在线。

一个 $n$ 个点 $m$ 条边的有向图，求最多能选择多少个点，使得任意两点不连通。

有 $n$ 个商店，每个商店中各有一个特殊物品，特殊物品会一直供应；按照时间顺序（令时间为 $\mathrm{day}$）有 $m$ 个下列事件：

1. 第 $s$ 个商店在当日新进一种价值为 $v$ 的商品，$\mathrm{day}++$；
2. 询问第 $L$ 到第 $R$ 的商店购买 $d$ 天内的商品价值 $\mathrm{xor} \ x$ 的最大值。

对于时刻 $1 \sim n$，要求支持：

1. 加入一个数 $a$；
2. 删除一个已加入的数 $a$。

求每个时刻所有数的最大异或和。

维护一个向量集合，在线支持：

1. 加入向量 $(x, y)$；
2. 询问 $[l, r]$ 中的向量与向量 $(x, y)$ 的点积最大值。

维护一个向量集合，支持：

1. 插入一个向量 $(x, y)$；
2. 删除插入的第 $i$ 个向量；
3. 查询当前集合与 $(x, y)$ 点积的最大值是多少，如果当前是空集输出 $0$。

一种构造方法，仅 $532$ 个点，$24115$ 条边的图，使得 Dinic, SAP, ISAP 运行时间均大于 $1s$，
$1198$ 个点，$120796$ 条边运行时间均超过 $1 \mathrm{min}$（当然也可能是我的最大流写得太菜）。

一个函数 $f(x)$，它满足：

1. $f(1) = 1$。
2. $f(p ^ c) = p \oplus c$（$p$ 为质数，$\oplus$ 表示异或）。
3. $f(ab) = f(a)f(b)$（$a$ 与 $b$ 互质）。

求 $\sum\limits_{i = 1} ^ n f(i) \bmod 1000000007$。

定义欧拉函数的变种

$$\phi(n, d) = \prod_{k = 1} ^ m (p_k ^ {e_k} + d)$$

特别的，$\phi(1, d) = 1$，求

$$\sum_{i = 1} ^ n \phi(i, d) \pmod {10 ^ 9 + 7}$$

求 $A = \sum\limits_{i = 1} ^ n \mu(i ^ 2), B = \sum\limits_{i = 1} ^ n \varphi(i ^ 2)$

求 $\sum\limits_{i = 1} ^ n \sigma_{0}(i ^ k)$，$n, k \leq 10 ^ {10}, T \leq 10000$。

扩展埃拉托色尼筛法可以在大约 $O(n ^ {\frac {2} {3}})$ （这里以实际运行效果估计，实际复杂度据说和洲阁筛一样）求出一般积性函数的前缀和，消耗 $O(\sqrt{n})$ 的空间。

要求支持 $2$ 种操作：

1. 向字典中加入一个串 $s$，其权值为 $v$（若重复算作多个串）。
2. 询问一个串 $t$，其中在字典中出现过的单词的权值和（相同单词应被多次计算）。

强制在线。

三模数 NTT 与拆系数 FFT

两个长度为 $10 ^ 5$ 级别的多项式相乘，对 $10 ^ 9$ 级别任意模数取模。

维护一片森林，要求支持加边，询问重心，询问所有树重心编号的异或和。

维护一个森林，每个点有一个函数 $f$，要求支持连接两个点，断开两个点，修改某个点的函数，询问路径上函数 $f(x)$ 的和。

给定一个字符串 $S$，定义一个位置 $i$ 的识别子串为包含这个位置且在原串只出现一次的字符串，求每个位置的识别子串的长度。

求在 $\bmod 10 ^ 9 + 9$ 的意义下，数字 $C$ 在 $\text{Fib}$ 数列的哪个位置，无解输出 $-1$。

给 $n$ 个人，每人有 $5$ 科成绩，给出 $q$ 个成绩查询，输出 $5$ 科都比要查询的这 $5$ 科低的数目。

给出 $n$ 个关键点，求出满足以下条件的点的个数及坐标：

• 距离它最近的关键点有至少 $k$ 个

有 $n$ 种物品，个数无限，价值为 $w$，价格为 $p$，要求支持单点修改，询问 $k$ 元能买的最大价值，要求优先购买能买的物品中价值最大的，相同价值选择价格小的。

给出一个序列，每次操作将 $[l, r]$ 染上一种颜色 $i$，问最后有多少种颜色。

给出一个序列，每个位置有同一个颜色，每个颜色有一个价值，要求支持单点修改，查询区间 $[l, r]$ 的权值和，相同颜色只算一次。

给出一个无向图，对于每条边，求必须选择这条边的情况下，使得原图连通的最小代价。

T2 Game

甲乙两个人轮流那一些物品，甲先手，他可以拿走 $1$ 或 $2$ 个物品。对于后面，若前一个人拿走 $k$ 个物品，当前的人可以拿走 $k$ 或 $k + 1$ 个物品，甲乙的策略都是让自己尽量比别人拿的物品的价值高，求最优策略下，甲最多比乙多拿多少？

一棵树，经过一条边花费 $c_i$ 的时间，某些点上有障碍，经过额外花费 $t_i$ 时间，每个节点有 $w_i$ 的价值，求 $T$ 秒后获得的最大价值。

求随机生成的一棵有根二叉树的叶子节点数的期望。

T1 建设图

给出一个无向图，求最少添加多少条边使得，无论删掉哪条边任意两点都可以互相到达。

给出 $n$ 个字符串，再给出 $n$ 个字符串，求一一匹配情况下 LCP 的最大长度和。

给定一个长度为 $n$ 的字符串，你需要在任意位置添加尽量少的字符，使新串是回文串。输出最少添加的字符个数以及新串。

T1 Fibonacci

询问一个数能否被分成两个 Fibonacci 数的乘积。

有 $n$ 个仓库，让 $m$ 个人来看管。一个仓库只能由一个人来看管，一个人可以看管多个仓库。
每个人有一个能力值 $p_i$，如果他看管 $k$ 个仓库，那么所看管的每个仓库的安全值为 $\lfloor \frac {p_i} {k}\rfloor$
如果某个仓库没有人看管，那么它的安全值为 $0$。所有仓库的安全值 $L$ 为所有仓库安全值的最小值
如果雇佣一个人的工资等于他的能力值 $p_i$。
从 $m$ 个人中选择一些人雇佣，问所有仓库的安全值最高是多少，在安全值最高的情况下，求雇佣的最少价钱。

有一个 $n \times m$ 的矩阵，请你选出其中 $k$ 个子矩阵，使得这个 $k$ 个子矩阵分值之和最大。注意：选出的 $k$ 个子矩阵不能相互重叠。

T1 打牌

给出一些数字，求最多能组成多少个对子 $(x, x)$ 或顺子 $(x, x + 1, x + 2)$。

给出一个字符串，输出其字典序最小的最长回文子序列。

给出一个字符串，把它分成 $k$ 块，块内可以任意排序，连续的相同字母算作一段，求最终字符串中的最小段数。

T1 购买板凳

有 $n$ 条信息，每条信息包含 $x$ 个人，这 $x$ 个人会在 $A$ 时间到达，$B$ 时间离开，每个人到达后会占用一个板凳，求至少要准备多少个板凳。

地主的傻儿子豆豆家很大很大，由很多个区域组成。其中有不少封闭的区域，豆豆觉得很不爽于是决定拆墙，把家打通使得他可以访问到每一个区域（包括家外面无限大的区域）。我们用 $N$ 个端点和 $M$ 条边来描述豆豆的家。第 $i$ 个端点的坐标为（$x_i, y_i$）,第 $i$ 条边连接端点 $A_i$ 和 $B_i$，拆除所需要花费的力气为 $C_i$ 。保证所有边只在端点相交，也就是这是一个平面图，也没有重边和自环。

现在豆豆想知道他最少一共需要花费多少力气？

现有一个长度为 $n$ 的序列 ${x_1, x_2, \cdots, x_n}$，要求支持两种操作：

1. 0 l r 表示将 $i \in [l, r], x_i \leftarrow x_i^2 \bmod p$
2. 1 l r 询问 $\sum\limits_{i = l} ^ r x_i$