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; }