BZOJ3612:[Heoi2014]平衡 整数划分

思路:

首先有两种情况,就是在中轴线处放不放,于是问题转化为在两侧分别放一些橡皮,使得距离之和相同.

我们令\(f[i][j]\)表示在一侧放橡皮,距离之和为\(i\),共放了\(j\)个橡皮的可行方案数.

不难转化为整数分解问题,也就是将整数\(i\)分解为\(j\)个不相同正整数,且每个正整数均不超过\(n\)的问题.

我们依旧分情况讨论:

[1]若划分的最小正整数为1,我们拿走最下面一行,转化为\(f[i-j][j-1]\).

[2]否则,我们拿走最下面一行转化为\(f[i-j][j]\).

不过最大的正整数不能超过\(n\),我们发现我们每次都是在最下面加上一行,那么如果加上后不合法,最后一列就应该是\(n+1\),于是不合法的方案数就应该是\(f[i-n-1][j-1]\).

于是\(f[i][j]=f[i-j][j]+f[i-j][j-1]-f[i-n-1][j-1]\)

记忆化搜索水过.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
int n,k,p,lim;
 
int f[100010][11];
 
int Solve(int i,int j){
    if(j==1)return(i>0&&i<=n)?1:0;
    if(i<=0||i<(1+j)*j/2||i>=j*n)return 0;
    if(f[i][j]!=-1)return f[i][j];
    return f[i][j]=((long long)Solve(i-j,j-1)+Solve(i-j,j)-Solve(i-n-1,j-1)+p)%p;
}
int main(){
    int T;cin>>T;
    register int i,j;
    while(T--){
        scanf("%d%d%d",&n,&k,&p);
        if(k==1){puts("1");continue;}
        memset(f,-1,sizeof f);
        for(i=0;i<=n*k;++i)f[i][0]=0;
        for(i=1;i<=n*k;++i)for(j=1;j<=k;++j)f[i][j]=Solve(i,j);//printf("n=%d m=%d t=%d\n",i,j,f[i][j]);
        long long res=0;
        for(i=1;i<=n*k;++i){
            for(j=1;j<k;++j){
                res=(res+(long long)f[i][j]*f[i][k-j])%p;
                res=(res+(long long)f[i][j]*f[i][k-j-1])%p;
            }
        }
        printf("%d\n",res);
    }return 0;
}