显然 $f(S)$ 即为 $m^{\mathsf{连通块个数}}$。

连通块是困难的，要搞容斥系数什么的好像也行，但这个数据范围过不去。

考虑转化一下命题，联通块内颜色相同 $\to$ 边的两点颜色相同。显然两命题等价。此时边就成了两个元素上的限制，表示一种二元关系。不妨设第 $i$ 条边表示的限制为 $p_i$。

则 $f(S)=\mathrm{sum}(\bigcap\limits_{i\in S} p_i)$，其中 $\mathrm{sum}(P)$ 表示限制集为 $P$ 的方案数。

显然只有机器人会处理交集这种限制。此时需要转换视角。发现 $(-1)^{|S|+1}$ 这个东西很像容斥系数，配上 $f(S)$ 化开后 RHS 的式子就更有容斥的感觉了。

写一下答案的式子：

$$\mathrm{ans}=\sum_{\emptyset \neq S\subseteq E} (-1)^{|S|+1}\times f(S)=\sum_{\emptyset \neq S\subseteq E}(-1)^{|S|+1}\times \mathrm{sum}(\bigcap_{i\in S} p_i)=\mathrm{sum}(\bigcup_{i\in E} p_i)$$。

并集是容易处理的。正难则反一下，算总方案减去所有条件都不满足的方案，即 $m^n-m^{\underline n}$。

计数问题，考虑 dp。

设 $f(i,j)$ 表示走到点 $i$，路径长度为 $j$ 时的方案数。状态数 $n^2\times c_i$，显然不行。

考虑优化状态。发现当且仅当 $j\in [\mathrm{dis}_i,\mathrm{dis}_i+k]$ 时有贡献，其中 $\mathrm{dis}_i$ 表示 $1\to i$ 的最短路长度。

此时 $f(i,j)$ 表示走到点 $i$，路径长度为 $\mathrm{dis}_i+j$ 的方案数。状态数 $nk$。

考虑判断无解。当且仅当存在 0 环，且 0 环上的点有合法路径时无解。正反跑一次最短路，把 0 边抽出来跑 tarjan 求 scc，对于每个大小 >1 的 scc 判断即可。

洛谷题解里提到，可以记忆化搜索，过程中判断这个状态是否入栈。然而如果这个状态不提供合法路径，这样判断就是错的。这是我的思考，不知道对不对。

对于剩下的图，显然不能 dijkstra 那样 dp 转移，考虑把状态集合抽象成一个 DAG，拓扑排序跑 dp 即可。但是这样有较多的无效边。感觉跑起来不会快。感觉记忆化搜索会好一些，但也不好说，毕竟拓扑常数小，记忆化搜索需要的栈空间很多，常数非常大。

时间复杂度 $\mathcal O(T(m\log m+nk))$。榜上一些 SPFA 跑得比我 dijkstra 快我是不理解的。应该是那个年代还没有针对 SPFA 构造 hack 数据的习惯。

首先直接按题意模拟一下，发现“所有质数都要被选上”这个条件很烦，因为选上一个卡牌后有很多质数会受到影响，非常不好做。换言之，题中的限制很强。

考虑正难则反，钦定一些质数使得它们 恰好 没有被选上，其它质数都被选上。然后会发现 恰好 这个条件还是很强，不好搞，直接上容斥，把 恰好

弱化成 一部分 被选上，另一部分不用管。这样限制条件就松了很多。

回到题目，$n\le 10^6$ 这个条件是唬人的，真正互不相同的数字只有 $2000$ 个，拿桶记一下数 $n$ 就可以扔了。

对于 $s_i\le 30$ 的部分分，显然可以状压预处理然后容斥计算。这为我们提供了一些思路。

[NOI2015] 寿司晚宴 这道题给出了一个相当经典的处理手段：一个数至多有一个 $\gt \sqrt n$ 的质因子，对于 $\le \sqrt n$ 的质因子状压，对于 $\gt \sqrt n$ 的质因子单独考虑。为了方便，称这类质因子为“大质因子”。

本题 $V=2\times 10^3$，发现 $\le \sqrt V$ 的质数只有 $2\sim 43$ 这 14 个，进一步地，$43\times 47\gt 2000$，所以 43 也不用参与状压，进一步压缩了状态。

然后统计，令 $f(i,j)$ 表示前 13 个质数没有被选的状态为 $i$，当前大质因子为 $j$ 时的方案数。预处理是简单的。

然后我们考虑容斥，容易发现容斥系数为 $(-1)^{|S|}$。

计算答案并不难。对于一个状态 $i$，枚举 $j\in [43,2000],j\in \mathbb P$，如果 $j$ 在询问集合中，那么有 $2^{f(i,j)}-1$ 的贡献（筛去空集），反之有 $2^{f(i,j)}$ 的贡献。

把询问集合存成 std::vector，每次就不用枚举 $j$，直接扫一遍 std::vector 然后统计答案，和容斥系数乘起来加到答案里即可。实现可以参考代码。

时间复杂度 $\mathcal O(\sum c_i\times 2^{13})$。

合格的签到题。

首先发现式子是一个 0-1 分数规划的模型，所以先二分答案 $mid$，男生 $i$ 和女生 $j$ 配对的价值为 $a_{i,j}-b_{i,j}\times mid$。

进一步地，发现男生和女生的关系形成一张二分图，并且男女双双配对，配对有权值，相当于二分图带权最大完美匹配。

可以使用 KM 算法求解，但我不会，学了一个费用流打了一下。核心思想就是把 EK 算法的 BFS 找增广路改为 SPFA 找增广路，顺便求一下最长路。

时间复杂度 $\mathcal O(n^4)$，在 COGS 的机器上可能有点难跑，但这只是理论上界，而且这可是二分图，SPFA 和 EK 都很难卡满，足以通过本题。

easy tea，不过有点小作弊：想完以后看了 Asm.Def 学长的评论才确定自己的思路是对的，并不是很自信。

考虑转化题意，求最多的说真话的人。

注意到如果有 $a_i$ 个人比 $i$ 低，有 $b_i$ 个人比 $i$ 高，说明 $i$ 的成绩排名 $\in [a_i+1,n-b_i]$。

将区间视作一条线段，然后把 $[l,r]$ 相同的线段合并，给 $[l,r]$ 这条线段赋权。本题就转化为了最大线段带权覆盖问题。$\rm dp + std::map$ 可以 $\mathcal O(n\log n)$ 地解决这个问题。

小陷阱：如果有超过 $r-l+1$ 个人的成绩排名 $\in [l,r]$，那么 $[l,r]$ 的权值为 $r-l+1$，$\rm dp$ 的时候取 $\rm min$ 判断一下就好了。

首先，01 背包是 NP 的，直接做不行，要关注题中的小性质。

发现 $C_i\le 300$，于是对 $C_i$ 分组，同组内价值降序排序，设为 $V_1\sim V_m$，那么如果选上 $V_k$，则必然选上 $V_1\sim V_{k-1}$，挺显然的。把它看作一个前缀和的形式。

然后发现 dp 方程可以各个同余类分开计算。

进一步的，一个同余类中的 dp 转移具有决策单调性。

感性理解一下，如果决策不具有单调性，那么会取的 $k$ 会更大，而我们对元素进行了降序排序，$k$ 更大是不优的。

决策单调性分治计算即可。

时间复杂度 $\mathcal O(kc\log k)$。