自动搬运

查看原文

来自洛谷，原作者为

	Mizuhara **

搬运于2025-08-24 21:22:48，当前版本为作者最后更新于2018-03-18 15:54:47，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

首先是一步本鶸想了很久也没有想到的操作。。。

因为将整行/列平移并不影响诸侯间的限制关系，

且题目又说了镜面和旋转的情况属于不同的方案，

那我们就可以把图案平移成我们想要的样子了。

那我们希望图案是什么样子？既然是dp,

我们当然希望能够得到没有后效性的图案。

也就是楼下dalao的图案。

因为每一列的长度都≥前一列的长度，

所以若前$j$列放了k-1个且第$k$个放在$i$列，

那么在这一列放一个的方案便是长度$lon[i]-(k-1)$.

若用$f[i][k]$表示前$i$列放了$k$个

且第$i$个放在第$i$列的方案数，则易得

$f[i][k]=\sum_{j<i}{f[j][k-1]*(lon[i]-(k-1))}$

其中$lon[i]$表示第$i$列的长度。

这样做是$O(n^3)$的.实际上可以优化到$O(n^2)$.

复杂度高一层是因为我们的状态选择的限制多了.

因为实际上,我们不需要第$k$个放在第$i$列这一条件。

我们设$f[i][k]$表示前$i$列放了$k$个的方案，则有：

$f[i][k]=f[i-1][k]+f[i-1][k-1]*(lon[i]-(k-1))$

原因很简单,取$f[i-1][k]$代表第$i$列放$0$个,

取$f[i-1][k-1]*(lon[i]-(k-1))$代表第$i$列放$1$个.

最终输出$f[2*n-1][k]$.

复杂度$O(n^2)$.

#include<iostream>
#include<algorithm>
#define p 504
using namespace std;

int f[210][210],lon[210];
int main(){
	int n,kk;cin>>n>>kk;
	if(kk>2*n-1){cout<<0;return 0;}
	for(int i=1;i<n;i++)lon[2*i-1]=lon[2*i]=2*i-1;
	lon[2*n-1]=2*n-1;
	for(int i=0;i<=2*n-1;i++)f[i][0]=1;//初始化
	for(int i=1;i<=2*n-1;i++)
	for(int k=1;k<=lon[i];k++){
		f[i][k]=f[i-1][k]+f[i-1][k-1]*(lon[i]-k+1);
		f[i][k]%=p;
	}
	cout<<f[2*n-1][kk];
	return 0;
}