【BZOJ3612】【HEOI2014】平衡 整数区划
题意：
有一个杠杆，半长为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);
}
}
原题面：
Ⅰ. 最小的数不为1：
好说。 直接由f[i-j][j]在底下加一行得到。就是图2。