题意：

有一个杠杆，半长为n，在（2n+1）个整数坐标各有一个质量相同的砝码。

现在给出n，然后再给出要取走的砝码个数，问使得最终杠杆依然平衡的最终方案数是多少。

（文末会给出原题帽）

分析：

数据范围不大，我们可以写整数划分。

f[i][j]表示将i划分成j个互不相同的正整数，且最大不超过n 的划分方案数。

这里说一下这道题的整数划分。

我们不妨先来反向思考一下。---------------------------------------------------------------------

首先考虑f[i][j]（下图每一列都代表一个数，高度就是数值）

它可以在底下添加一行，进行转移

分为两种情况：

Ⅰ. 转移过后最小数不为1

Ⅱ. 转移过后最小数为1

然后f[i][j]可以向这两个方向转移。

而我们还需要保证最大数不能大于n，那么如下图

在最后加入一层，使得当前所有整数都+1时，发现出现了一个101，而不妨当作n是100

那么显然我们可以很方便地清掉这个数带来的情况。

即当前是f[i][j],那么最后一列是大于n的情况显然只能是有一个整数n+1

不看这个n+1，情况数是f[i-(n+1)][j-1] ,我们把这个情况集删掉就好了。

正向考虑：-----------------------------------------------------------------------------------

首先不妨把刚才的图片按顺序记作图1、2、3、4。

我们把f[i][j]（图1）这么多方案分成两种情况：

Ⅰ. 最小的数不为1：

好说。 直接由f[i-j][j]在底下加一行得到。就是图2。

此时原来划分出来的整数不同，新的这些整数显然依然不同。

Ⅱ. 最小的数为1：

那么显然它可以由f[i-j][j-1]转移得到，

即在f[i-j][j-1]代表图形下面整体+1，最后加上一个整数1，即图3。

注意此时f[i-j][j-1]代表的所有图形整数都不同（性质/定义），那么新加1后所有整数依然不同，且均>=2

这个时候再来个整数1，依然满足所有整数不同。

但是我们注意到还需要让最大数不能超过n，

所以有了图4。

也就是我们要减去最大数超过n的情况，方法前文图下有说明。

这道题难点解决了。

现在说一下其它细节：

f[i][j]算出来后直接暴力枚举两边的权值，及用点个数（不要忘了中心支点）

然后check。end。

代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 101000
#define M 15
using namespace std;
int n,m,p,w;
int f[N][M]; // f[i][j] 表示
//将i划分成j个互不相同的正整数，
// 且最大不超过n 的划分方案数
int main()
{
	int i,j,k,g;
	f[0][0]=1;
	for(scanf("%d",&g);g--;)
	{
		scanf("%d%d%d",&n,&m,&p);
		if(m==1)
		{
			puts("1");
			continue;
		}
		w=n*(m-1);
		for(i=1;i<=w;i++)
			for(j=1;j<m;j++)
			{
				f[i][j]=(i>=j?(f[i-j][j]+f[i-j][j-1]):0);
				f[i][j]=(i>=n+1)?(f[i][j]-f[i-n-1][j-1]):f[i][j];
				f[i][j]=(f[i][j]%p+p)%p;
			}
		long long ans=0;
		for(i=1;i<=w;i++)
			for(j=1;j<m;j++)
				ans+=f[i][j]*f[i][m-j],ans%=p;
		for(i=0;i<=w;i++)
			for(j=1;j<m-1;j++)
				ans+=f[i][j]*f[i][m-1-j],ans%=p;
		printf("%lld\n",ans);
	}
}

原题面：

【BZOJ3612】【HEOI2014】平衡 整数划分、