题目
【题目描述】
最开始有4个梯子，高度都为n，也就是每个梯子都有n层脚蹬的横木。小明想要对梯子进行改造（撤掉一些脚蹬用的横木），要满足以下两个条件。 1：撤掉一些横木之后，要保证每一层4个梯子中有且仅有1个梯子在这一层是有横木的。 2：梯子上面连向房顶，小明希望存在至少一个梯子能通过它爬到房顶（梯子之间距离较远，不能爬的过程中转换梯子），其中小明每次能至多爬h的高度，也就是从地面上（地面高度为0）可以达到高度为1、2……h的横木上，以及只可以从n-h+1、n-h+2……n高度的横木上爬到房顶（房顶高度为n+1）上去。
也就是说在撤掉一些横木之后，要求存在一个梯子，它的剩下的第一个横木是不超过h的高度，剩下的最后一个横木是大于等于n-h+1的高度，中间的任意两个相邻剩下的横木之间相差高度不超过h。
小明现在想知道满足条件的撤横木的方案数，答案对10^9+9取模。 其中两个方案不同当且仅当：存在某一层在两个方案当中，他们各自保留的那一根横木在不同的梯子上。
【输入格式】
第一行两个整数 n,h。
【输出格式】
一行一个整数,表示合法的方案数对10^9+9取模的结果。
【样例输入1】
5 1
【样例输出1】
4
【样例解释1】
因为这个间隔的上限是1，并且每一层只能留一个横木所以一组合法的方案肯定是只有一个梯子保留了所有的横木，其他的梯子没有保留任何一根横木，其中梯子数是4，所以答案也就是4。
【样例输入2】
4 3
【样例输出2】
256
【样例解释2】
我们会发现对于任意一种摆放方案，都是合法的，所有的摆放方案正是4^3。
【数据范围】
对于 40%的数据,n<=10（数据具有阶梯性）。
对于 70%的数据,n<=300,h<=min(n,15)。
对于 100%的数据,n<=1000,h<=min(n,30)。
题解
最恶心的就是计数题了……
令$f_{i,a,b,c,d}$表示第$i$层，第$1,2,3,4$个梯子最上面到当前踏板距离分别是多少，每次从上一层转移，从$1\rightarrow h$枚举，是$O(nh^4)$的，复杂度够呛
令$f_{i,0/1,a,b,c}$表示第$i$层，第$1$个梯子是否能到达这一层，第$1,2,3,4$个梯子最上面到当前踏板距离分别是多少，能到达的时候随便转移，不能到达的时候枚举$2,3,4$哪个来放这一层，复杂度是$O(nh^3)$
因为每个梯子是不同的，最后答案要$\times 4$
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
using namespace std;
const int MAX=1e3+5,mod=1e9+9;
int n,h;
int f[2][2][31][31][31];
int main()
{
scanf("%d%d",&n,&h),f[1][1][1][1][1]=1;
for(int i=2;i<=n;++i)
{
memset(f[i&1],0,sizeof(f[i&1]));
for(int j=0;j<=1;++j)
for(int k=1;k<=h;++k)
for(int l=1;l<=h;++l)
for(int g=1;g<=h;++g)
if(f[!(i&1)][j][k][l][g])
{
int qwq=f[!(i&1)][j][k][l][g],K=min(k+1,h),L=min(l+1,h),G=min(g+1,h);
f[i&1][j][K][L][G]=(f[i&1][j][K][L][G]+qwq)%mod;
f[i&1][k<h][j==1?1:h][L][G]=(f[i&1][k<h][j==1?1:h][L][G]+qwq)%mod;
f[i&1][l<h][K][j==1?1:h][G]=(f[i&1][l<h][K][j==1?1:h][G]+qwq)%mod;
f[i&1][g<h][K][L][j==1?1:h]=(f[i&1][g<h][K][L][j==1?1:h]+qwq)%mod;
}
}
int ans=0;
for(int i=0;i<=1;++i)
for(int j=1;j<=h;++j)
for(int k=1;k<=h;++k)
for(int l=1;l<=h;++l)
ans=(ans+f[n&1][i][j][k][l])%mod;
return printf("%d",int(ans-f[n&1][0][h][h][h]+mod)%mod*4ll%mod),0;
}
