P1240 诸侯安置

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

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

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

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

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

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

也就是楼下dalao的图案。

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

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

那么在这一列放一个的方案便是长度.

若用表示前列放了个

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

其中表示第列的长度。

这样做是的.实际上可以优化到.

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

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

我们设表示前列放了个的方案，则有：

原因很简单,取代表第列放个,

取代表第列放个.

最终输出.

复杂度.

#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;
}