炫教的题解：

为叙述方便，我们不妨设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分