Description:

在 $[-n,n]$ 中选 $k$ 个数使他们的和是 $0$ 的方案数。

$1\le n \le 10000$ $1\le k \le 10$

Solution:

整数划分数，记 $f[i][j]$ 表示和为 $i$ ，分成 $j$ 个数的方案，则 $f[i][j]=f[i-1][j-1] + f[i-j][j]$ 。

由于两两不同，所以 $f[i][j]=f[i-j][j] + f[i-j][j-1]$ 分别代表给所有数加一和给所有数加一再加一个一。

由于只能在 $[-n,n]$ 中选，所以如果有超过 $n$ 的应减掉，如果 $i > n$ ，那么一定有一种划分方式使得有超过 $n$ 的数，由于每次只给所有数加一，所以产生的大于 $n$ 的数一定是 $n+1$ ，只要减掉 $f[i-(n+1)][j-1]$ 即可，表示去掉一个数字 $n+1$ 之后的方案数。

统计答案时，枚举小于 $0$ 中的数选几个，则 $ans += f[i][j]\times f[i][k-j]$ ，由于可以放一个在中间，则 $ans+=f[i][j]\times f[i][k-j-1]$ 。

如果 $k==1$ 还要加上只放在中间的方案数。

Code:

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int testcases;

int n,k,p;

int f[100010][11];

int main()

{

    scanf("%d",&testcases);

    for(int t = 1;t <= testcases;++t)

    {

        scanf("%d%d%d",&n,&k,&p);

        f[0][0] = 1;

        for(int i = 1;i <= n * k;++i)

        {

            for(int j = 1;j <= i && j <= k;++j)

            {

                f[i][j] = (f[i - j][j] + f[i - j][j - 1]) % p;

                if(i > n)f[i][j] = (f[i][j] - f[i - (n + 1)][j - 1] + p) % p;

            }

        }

        int ans = 0;

        for(int i = 1;i <= k * n;++i)

        {

            for(int j = 1;j < k;++j)

            {

                ans = (ans + f[i][j] * f[i][k - j] % p) % p;

                if(j < k - 1)ans = (ans + f[i][j] * f[i][k - j - 1] % p) % p;

            }

        }

        printf("%d\n",(ans + (k == 1)) % p);

    }

    return 0;

}