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

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

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

回到题目，$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)$。

Editorial of srf.

不知道状压可不可行阿，先说一个我的错误状压思路：

设 $f(i,S)$ 表示前 $i$ 个点的叶子节点状态为 $S$，最大深度在点 $i$ 处取得的方案数。然后会发现这个东西没办法转移。

继续瞎搞，考虑枚举深度 $d$，划分为若干层，进行状压 dp，但是仍然没啥好方法转移。也可能是我菜。

树上深度计数考虑组合数。计算总数，最后除以 $(n-1)!$。

设 $f(i,j)$ 表示 $i$ 个点的树，深度为 $j$ 的方案数。

因为点 $2$ 一定接在 $1$ 上，所以我们枚举点 $2$ 的子树大小及深度，然后合并其它子树和点 $2$ 的子树。这样显然不会算重。

这个过程可以保证方案是合法的，只关心点编号之间的大小关系。用组合数辅助计算。

取整可以用 long double 或者 __int128 存一下。

时间复杂度 $\mathcal O(n^4)$。

观察一下样例，不难发现答案单调不升。且注意到，一对点对 $(i,j)$ 至多贡献一次。

因此我们猜想，若 $G_k$ 中 $(i,j)$ 有贡献，则 $G_{k-1}$ 中 $(i,j)$ 仍有贡献。这不难证明（好像 [CSP-S 2021] 廊桥分配 也有这种思想）。

上述性质可以引出一个更强的判定条件，继续进行扩展，发现图 $G$ 中 $(i,j)(i\le j)$ 有贡献当且仅当存在两条路径 $P:i\to j,Q:j\to i$ 使得 $P,Q$ 中经过的编号最小的点编号 $\ge i$。

这条性质有点隐蔽，但证明非常简单，考虑反证法，假设有一个点 $k$ 在 $i\to j$ 的路径上，使得 $k\lt i$，那么就存在 $k\to j$ 和 $j\to i\to k$ 两条路径，则 $(k,j)$ 对答案产生贡献，$k$ 已被删除，与假设相悖。原命题成立。

然后我们考虑计算答案。根据上述性质，我们可以倒着加边，枚举判断每个点对最早在何时联通，然后后缀和计算答案。

但是这样是 $\mathcal O(n^2m)$ 的，考虑优化。

一种方法是直接倒序 Floyd，中途判断答案，但 $\mathcal O(n^3)$ 的复杂度很卡常，坏。

（不过这题数据比较水，其实也很难卡满复杂度，lg 题解中看到，似乎倒序加边跑 dijkstra，用斐波那契堆就可以过。）

考虑优化判断联通性的过程。枚举点 $i$，计算所有 $(i,j)(j\ge i)$ 的贡献。

发现 $(u,v)$ 在原图联通，等价于 $v$ 在原图和反图均可达 $u$。

将原图反图分开计算。先考虑原图上加入一条边 $u\to v$ 的影响。

发现若 $u,v$ 原本都与 $i$ 联通，则 $u\to v$ 这条边无意义，扔掉。

反之，若 $v$ 原本不联通，分情况讨论：

若 $u$ 原本联通，则 $v$ 本身和它所连的点变为联通状态。bfs 一遍即可。

反之，$u\to v$ 这条边以后可能产生贡献，先保存下来。

反图类似处理，显然 bfs 过程中答案会发生变化，途中计算即可。

不难发现这样每条边只会被遍历 1 次，故时间复杂度 $\mathcal O(n(n+m))$。稍有卡常，但问题不大。还有能完美通过本题的 bitset 做法，但是我学不会 /ll。

upd：新增了 bitset 的代码，具体做法可以去 Alex_Wei 老师的题解 中学习。