C 题有个输入文件不小心删除了最后一行导致奇怪的问题，向大家道歉，请大力喷我.jpg。

有问题请提，我会尽力解答= =

A

模拟。

每组数据时间复杂度 。
42651533

B

范围较大无法模拟，需要优化。

先忽略玩家血量，怪物被打死时必然是：玩家攻击 次，玩家被怪物攻击 次，怪物回血 次。

找到最小的 判断玩家血量是否足够，注意取整。

每组数据时间复杂度 。

42651620

C

经典 NPC 问题

状态压缩 DP ，有一个较显然的 做法， 表示装下 这个集合最小需要多少箱子， ，最后判断是否满足 ，但无法通过。

优化：令 和 分别表示装下 这个集合最少需要多少箱子、最后一个箱子的剩余承重量（可以将 pair<dp1[S],dp2[S]> 理解成 TSP 问题的"距离"，by 验题人）。

每组数据时间复杂度 。

42651549

D

求出每个前缀/后缀的最长回文串长度，枚举分隔点，左边前缀+右边后缀取 max 。

回文自动机：加入每个字符之后，last 结点的 len 即为以当前字符为末尾的最长回文子串长度，正反串各求一次即可。时间复杂度 ， 为字符集大小。

manacher 做法类似但细节较多。

42651553

E

• 只有子树异或和为 或 的点才可能对答案产生贡献，其他的点可以不用考虑。

令 表示以 为根的树删掉偶数/奇数条连向 子树 xor 和为 的儿子 的边，从而划分成奇数/偶数个符合条件的连通块的方案数，转移代码如下：

    ll dpu0 = dp[u][0], dpu1 = dp[u][1];
    dp[u][0] = (dpu0 * dp[v][0] + dpu1 * dp[v][1]) % mod;
    dp[u][1] = (dpu0 * dp[v][1] + dpu1 * dp[v][0]) % mod;

这个做法要额外考虑向父亲的边。应该有更好理解的做法。

每次转移 ，总时间复杂度 。

42651557

F

易知

可推得

可以分块（设块大小为 ，为了方便计算复杂度假设 ）求出不同区间长度的 函数取值，再结合组合数系数得到 的真实值。

具体过程为：预处理出长度是 的倍数的 值，利用 FFT 优化该过程，该部分复杂度 ；查询时结合组合数系数依照 即可 回答单个询问。

取 最优，时间复杂度 。

42651646