[HDU 5180]chess 组合+轮廓线状压dp

题面：http://acm.hdu.edu.cn/showPRoblem.php?pid=5180

体会到了轮廓线的边界情况的可怕。。。

题意：n*n国际象棋棋盘上放k个车和任意数量的王，要求车不能吃车，车不能吃王，王不能吃王，王可以吃车，问方案数模1e9+7

1<=n<=15,0<=k<=15

题解：

法1：暴力状压每列4种状态：没有棋子，最后一格有个王，前面有个王，有个车。状态O(n*4^n)，转移O(4^n)，时间复杂度O(n*4^2n)，空间复杂度O(4^n)直接爆炸

法2：法1改成轮廓线dp（或者说分步式转移），转移变成O(1)，时间复杂度O(n^2*4^n)，空间复杂度O(4^n)，内存怎么优化一番说不定能打表

法3：考虑到王的方法不影响车的摆放，直接考虑车的方法，发现无论车怎么放，王能放的位置恰占据了棋盘的一个(n-k)*(n-k)子矩阵，且子矩阵的每个联通块互不影响，行列也互不影响，于是可以预处理i*j连通块内的放王方式再用全排列+可重排列+可重组合在行列分别枚举(n-k)的拆分算。这个又是一个状压dp，用轮廓线可以优化到O(n^2*2^(n+1))（注意因为王的攻击是8个方向需要记一行多1格的状态，边界情况无比恶心）。最后复杂度O(n^2*2^(n+1)+T*k^2*(n-k的拆分数)^2)，n-k的拆分数在15以内最多两位数所以随便暴力一番就好了。。

代码：

#include<cstdio>#include<cstring>#include<cstdlib>#include<algorithm>#define lbt(i) ((i)&(-(i)))using namespace std;typedef long long LL;const LL md=1000000007LL;int T,n,k;struct DV{	int c,a[17];	DV(){c=0;memset(a,0,sizeof(a));}}Sit[17][17][31];int c[17][17];bool ava[40000];LL f[17][17],dp[2][40000][2],fac[31],inv[31],facinv[31];#define C(i,j) (((fac[(i)]*facinv[(j)])%md*facinv[(i)-(j)])%md)void ini(){	DV tmp;	Sit[0][0][++c[0][0]]=tmp;	for(int i=1;i<=15;i++)	for(int j=1;j<=15;j++)	{		for(int l=1;l<=c[i-1][j-1];l++){			Sit[i][j][++c[i][j]]=Sit[i-1][j-1][l];			Sit[i][j][c[i][j]].a[++Sit[i][j][c[i][j]].c]=1;		}		for(int l=1;l<=c[i-j][j];l++){			Sit[i][j][++c[i][j]]=Sit[i-j][j][l];			for(int p=1;p<=Sit[i][j][c[i][j]].c;p++)			Sit[i][j][c[i][j]].a[p]++;		}	}	ava[0]=true;	for(int i=1;i<(1<<15);i++)ava[i]=ava[i^lbt(i)]&&!(i&(lbt(i)<<1));	for(int i=1;i<=15;i++)	for(int j=1;j<=15;j++){		memset(dp,0,sizeof(dp));		int mx=(1<<j);		dp[0][0][0]=1;		for(int l=1;l<=i;l++){			for(int o=1;o<=j;o++){				int mm=((l-1)*j+o)&1,r=((1<<o)-1);				for(int p=0;p<mx;p++){					dp[mm][p][0]=dp[mm][p][1]=0;					if(!ava[p&r]||!ava[(p>>o)]||(o!=j&&(p&1)&&(p&(mx>>1)))||(l==1&&(p>>o)))continue;					dp[mm][p][0]=dp[mm^1][p>>1][0];					if(!(p&1)||o==1)dp[mm][p][0]=(dp[mm][p][0]+dp[mm^1][p>>1][1])%md;					if(!(p&1)&&l>1&&!((p&2)&&o>1)&&(!(p&(mx>>1))||o==j)){						dp[mm][p][1]=dp[mm^1][(p>>1)|(mx>>1)][0];						if(o==1)dp[mm][p][1]=(dp[mm][p][1]+dp[mm^1][(p>>1)|(mx>>1)][1])%md;					}				} 			}		}		LL tmp=0LL;		for(int p=0;p<mx;p++)tmp=(tmp+dp[(i*j)&1][p][0]+dp[(i*j)&1][p][1])%md;		f[i][j]=tmp;	}	fac[0]=facinv[0]=1;	inv[1]=1;	for(int i=2;i<=30;i++)inv[i]=((md-md/i)*inv[md%i])%md;	for(int i=1;i<=30;i++)fac[i]=(fac[i-1]*i)%md;	for(int i=1;i<=30;i++)facinv[i]=(facinv[i-1]*inv[i])%md;}LL wk(){	LL ans=0LL;	if(n>k){		int tot=n-k;		for(int i=1;i<=min(tot,k+1);i++){			for(int j=1;j<=c[tot][i];j++){				DV A=Sit[tot][i][j];				LL tmpa=1LL;				tmpa=(tmpa*fac[i])%md;				for(int q=1,t0=0;q<=i;q++)				if(q==i||A.a[q+1]!=A.a[q])tmpa=(tmpa*facinv[q-t0])%md,t0=q;				tmpa=(tmpa*C(k+1,i))%md;				for(int l=1;l<=min(tot,k+1);l++){					for(int p=1;p<=c[tot][l];p++){						DV B=Sit[tot][l][p];						LL tmp=tmpa;						tmp=(tmp*fac[l])%md;						for(int r=1,u0=0;r<=l;r++)						if(r==l||B.a[r+1]!=B.a[r])tmp=(tmp*facinv[r-u0])%md,u0=r;						tmp=(tmp*C(k+1,l))%md;						for(int x=1;x<=i;x++)						for(int y=1;y<=l;y++)						tmp=(tmp*f[A.a[x]][B.a[y]])%md;						ans=(ans+tmp)%md;					}				}			}		}	}	else if(k==n)ans=1LL;	return (ans*fac[k])%md;}int main(){	scanf("%d",&T);	ini();	for(int i=1;i<=T;i++){		scanf("%d%d",&n,&k);		printf("%d/n",(int)wk());	}	return 0;}