orz ysx

Problem A:

题意：
q次询问：能否用形如 x = p1 * p2 (p1,p2均为质数且可以相等) 的数相加得到给定的数n。

题解： 当n <= 20 时,只有1,2,3,5,7,11无解，其余均有解。
当n > 20 时,因为n = (n-4) + 4 = (n-4) + 2 * 2,而(n-4)这个数>=16,是一定有解的。
所以,我们证明了对于任意的正整数n,
只有n = 1,2,3,5,7,11时无解，其余均有解。
那么我们只需要在每组数据中判断一下n是否等于1,2,3,5,7,11中的任意一个即可。
复杂度O(q).

Problen B:

题意：
q组数据。
给你一个长为n的非负数序列a。
定义一个区间的权值为区间的异或和。
定义一个划分的权值为分出的区间的权值的按位与的值。
要求至少把序列分成m个非空字段,求满足条件的划分的最大权值。

题解：
因为异或运算具有交换律且（x异或x = 0）,所以区间异或和可以由两个前缀异或和异或得到。
考虑从高位到低位确定答案的二进制位,然后考虑判断是否能分成至少m段。
如何判断是否能分成至少m段?
"能分成至少m段"与"最多能分成的段数>=m"等价。
令dp[i] = "a[1..i]这一段数最多能分成多少段"
转移就是直接枚举上一段的末尾j,如果[j+1,i]可以组成一段,那么就把dp[i] = max(dp[i],dp[j] + 1);
这样DP的复杂度是O(n^2)。
总复杂度就是O(q log(值域) DP) = O(30qn^2) ≈ 3.6 * 10^8,因为常数较小可以过。

值得一提的是,直接O(N^3)DP是错误的。因为它不满足最优子结构。

Problem C:

题意： 定义一个排列 a 的价值为满足|a[i]-i|<=1 的 i 的数量。
给出三个正整数 n,m,p，求出长度为 n 且价值恰好为 m 的排列的个数对 p 取模的结果。
T组询问,p事先给出。

题解：
因为n,m <= 2000,而且p是事先给出的,所以我们可以一次性预处理出n,m <= 2000的答案。

考虑一个长度为i的排列如何变成长度为i+1的排列。
一种情况是我在它末尾加入了一个数i+1,另一种情况是我用i+1替换掉了原来排列中的一个数，然后把被换掉的数放到排列的末尾。
那么,这个排列权值的变化就是：
第一种情况：在它末尾加入了一个数i+1，权值+1。
第二种情况：用i+1替换掉一个数，权值 += 加的贡献 - 换掉的数的贡献。

在DP当中，我们只需要考虑替换掉的数是否是i,以及i是否在位置i/i-1即可。总共有5种本质不同的状态，分类讨论转移即可。
复杂度O(nm)。