BZOJ 3195 DP

http://www.cnblogs.com/CXCXCXC/p/5093584.html

//By SiriusRen
#include <cstdio>
using namespace std;
int n,m,K,mod=1000000007,f[33][33][666][9];
int main(){
    scanf("%d%d%d",&n,&m,&K);
    f[1][0][0][0]=1;
    for(int i=1;i<=n;i++)
        for(int j=0;j<=m;j++)
            for(int k=0;k<1<<(K+1);k++){
                for(int l=0;l<K;l++){
                    (f[i][j][k][l+1]+=f[i][j][k][l])%=mod;
                    if(i-K+l>0)(f[i][j+1][k^(1<<l)^(1<<K)][l]+=f[i][j][k][l])%=mod;
                }
                if(!(k&1))(f[i+1][j][k>>1][0]+=f[i][j][k][K])%=mod;
            }
    printf("%d
",f[n+1][m][0][0]);
}