bzoj3195:[Jxoi2012]奇怪的道路

传送门

显然可以发现把\(k\)状压
显然可以发现三维的dp，\(f[i][j][k]\)代表当前到\(i\)，已经连了\(j\)条边，当前\(i\ to\ i-k\)奇偶性为\(k\)，然而会重复算
所以再加一维\(t\)，表示上一次连的边为\(i->i-k+c\)
代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
void read(int &x) {
    char ch; bool ok;
    for(ok=0,ch=getchar(); !isdigit(ch); ch=getchar()) if(ch=='-') ok=1;
    for(x=0; isdigit(ch); x=x*10+ch-'0',ch=getchar()); if(ok) x=-x;
}
#define rg register
const int mod=1e9+7;
int n,m,k,f[32][32][1<<9][9];
int main()
{
    read(n),read(m),read(k);
    int tot=1<<(k+1);
    f[2][0][0][0]=1;
    for(rg int i=2;i<=n;i++)
        for(rg int j=0;j<=m;j++) 
            for(rg int y=0;y<tot;y++)
            {
                for(rg int t=0;t<k;t++)
                {
                    (f[i][j][y][t+1]+=f[i][j][y][t])%=mod;
                    if(j<m&&i-k+t>=1)(f[i][j+1][y^(1<<k)^(1<<t)][t]+=f[i][j][y][t])%=mod;
                }
                if(!(y&1))f[i+1][j][y>>1][0]=f[i][j][y][k];
            }
    printf("%d\n",f[n+1][m][0][0]);
}

bzoj3195:[Jxoi2012]奇怪的道路

原文：https://www.cnblogs.com/lcxer/p/10507423.html