【泉七培训-郑予凡】子集

2014年6月14日8130

炫教的题解:

为叙述方便,我们不妨设S={-n,-n+1,…,n}。本题就转化为求解∑χ(A)。其中求和式取遍S的k元子集A,而χ(A)当A的元素之和为0时返回1,否则返回0。

我们给出一些在比赛过程中解决本题的常见的算法。

【算法1:枚举】

顾名思义,这个算法直接枚举所有可能的A,然后逐一考察χ(A)。

期望得分:10

【算法2:动态规划】

记dp[a][b][c]为“从-n到n,当前已枚举到a∈S并已考虑完其是否在A中,已经确定了b个数在集合A中,这b个数之和为c”的方案数。易见答案就是dp[n][k][0] mod p。而边界条件和转移方程不难列出。当然,在实际程序设计过程中,dp数组要处处 mod p。

期望得分:30

【算法3:找规律/数学推导】(针对k=3的数据)

如果有尝试去找k=3时答案的规律,容易得到当n从1,2,3,…开始,答案依次取下列数:

1,2,5,8,13,18,25,32,41,50,…

可以发现规律Ans_3(n) = [n^2/2],其中[x]表示最小的大等于x的整数。

当然,也可以通过数学推导来得到这个公式。那么对n的奇偶性进行讨论就不难快速计算Ans_3(n) mod p。

期望得分:10

【算法4:数学推理】(针对p=2的数据)

注意到当p=2时实际上是要我们给出答案的奇偶性。

不难发现,对于一个合法方案A={a_1,a_2,…,a_k},我们可以用另一个合法方案A’={-a_1,-a_2,…,-a_k}与其配对。故而答案总为偶数。⋯⋯但是这显然与事实不符。这是因为有一些方案A是不可配对的,其原因是由于对于这些A有A’=A。那么我们只需要考虑这些A即可。(其他的A都已两两配对,不需考虑)不难得出这些A的总数是C(n,[k/2]),其中C(N,M)是组合数而[x]表示最大的小等于x的正整数。问题就转变为求C(N,M) mod 2。注意到N<=10000且M<=5,直接使用组合数的递推公式来求解即可。

期望得分:10

至此,整合算法2、3、4,总共可以得到50分。这也是我设定的理想中的非完美算法可以达到的最高分数。接下来的两个算法均是完美(满分)算法。

【算法5:动态规划II】

普通的动态规划思路在算法2即已达到极限,所以我们应该寻求另一种动态规划的思路。

容易知道,χ(A)=1当且仅当A中正数绝对值之和等于负数绝对值之和。方便起见,我们暂时不考虑0属于或不属于A。(如果不考虑0可做,那么考虑0依然可做)若枚举A中正数个数l,问题就转变为:

“求满足∑a_i=∑b_i的序列1<=a_1<a_2<…<a_l<=n与1<=b_1<b_2<…<b_(k-l)<=n个数。”

在算法2中,我们采取的基本思路是逐个确定每个数是否在A中。在这里,我们转换一下思路,我们同时来确定所有的a_i和b_i。当然,这样算法就退化成了枚举。于是,我们采取折衷的策略:每次同时确定所有a_i和b_i的一个二进制位!

有了这样的想法,就不难设计出一个状态压缩动态规划算法。为了保证1<=a_1<a_2<…<a_l<=n与1<=b_1<b_2<…<b_(k-l)<=n以及最后能有∑a_i=∑b_i,我们需要表示状态的两个量opt_A和opt_B来记录一些关于a_i与b_i(还有与n)的大小关系,以及它们的和的进位情况的信息。记dp[j][opt_A][opt_B]为“已经从低位至高位确定到所有a_i和b_i和前j个二进制位,状态信息分别为opt_A与opt_B,目前保证在只考虑每个数的前j个二进制位的情况下∑a_i=∑b_i”的方案数。这样,边界条件与状态转移方程也不难列出。易见,答案就是dp[∞][X][X],其中X代表所有数均已严格分出大小且已无进位。当然,在实际程序设计过程中,dp数组要处处 mod p,且答案应该取dp[20][X][X]为妥。(因为n<=10000且k<=10,任一方案中的所有数绝对值相加不可能超过2^19)

在dp转移的时候,直接暴力大转移而不逐个转移,从而导致复杂度因子从2^k升为2^(2k),只能拿到60分。(比如配套标程中的std_clj.cpp,我不确定你们看到这份解题报告的时候能不能拿到这个程序)当然,配合算法4还是可以拿到70分的。

期望得分:100~60

【算法6:找规律II+程序辅助】

如果我们固定k,考察数列{A_k(n)}(去掉开头的k项),会发现:它们都满足线性递推关系!进一步地,这个线性递推关系的阶数是O(k^2)。那么,我们就可以使用算法2,再辅以高斯消元法来求出k为某固定值时{A_k(n)}满足的线性递推方程。

利用算法2计算初值,再辅以递推式,可以轻松计算出答案。

附注:如果选手直觉较为敏锐,还可以发现 {A_k(n)}(去掉开头的k项)满足的线性递推关系的特征方程为:

(x-1)(x^2-1)(x^3-1)…(x^k-1) = 0

(注意,此处并不一定是最简线性递推关系。举个例子:斐波那契数列同样满足F_n = 2F_(n-2)+F_(n-3)。)

期望得分:100

蒟蒻hzwer水平太低,只能写40分