[UVa 12371]Guards

這題$N$好大，$K$好小，疑那我們能不能構造出$O(NK)$的算法呢XD

考慮$DP[n][k]$代表$n*n$的正方形分成$k$群的答案
於是乎我們得到以下邊界條件：
$if\ n<2k$，$DP[n][k]=0$
$if\ n=2k$，$DP[n][k]=\prod_{i=1}^{k}(2i-1)\binom{2i}{2}$
其中，$DP[2k][k]$可以用$DP[2(k-1)][k-1]*(2k-1)*\binom{2k}{2}$遞推出來(不過直接算也是OK，反正$k$只到50而已嘛XD)

再來考慮$n>2k$時的情況怎麼從$DP[n-1][k]$算出來
可以發現，當我們加入新的一行和一列後，固定新列在最底下，新行則有$n$個插入位置，假設插入後的位置是$x_{0}$好了
那麼，我們可以在$(x_{0},n)$放個守衛，再隨意找一個$x_{1}\neq x_{0}$，在$(x_{1},n)$再放個守衛，這時第$x_{1}$行變成了三個守衛，分別在第$y_{0}$、$y_{1}$、$n$列
怎麼辦呢？
只要從$(x_{1},y_{0})$、$(x_{1},y_{1})$中選一個(假設選$y_{i}$)守衛解雇，然後在$(x_{0},y_{i})$這個位置新增一個守衛就好了(還記的第$x_{0}$行是新行只有一個守衛吧XD)

上述計算方式會有重複，也就是第$x_{0}$行和第$x_{1}$行是對稱的，因此要除以2
我們得到$DP[n][k]=DP[n-1][k]*\frac{2n(n-1)}{2}$

可是...會發現，第$n$行的那群守衛所屬的守衛群大小(定義守衛群大小為其覆蓋的行數或列數)一定$>2$(因為是和另一個守衛群合併)
那第$n$行所屬的守衛群大小$=2$的情況怎麼辦？
可以從$DP[n-2][k-1]$來轉移！
這次，我們一次加入兩行兩列，這些行和列自成一個大小為2的守衛群
一列要固定在第$n$行，另一列則有$n-1$種選擇
兩行有$\frac{n(n-1)}{2}$種排列方式
因此當$k>1$時，$DP[n][k]$還得再加上$DP[n-2][k-1]*(n-1)*\binom{2i}{2}$

使用記憶化搜索實現應該會比較方便

時間複雜度：$O(NK)$

code:

#include<cstdio>
#include<cassert>
using namespace std;
typedef long long LL;
const LL MOD=1000000007LL;
LL DP[100001][51];
LL GetDP(const int n,const int k)
{
    if(n<k*2)return 0LL;
    assert(2<=n&&n<=100000&&1<=k&&k<=50);
    LL &ans=DP[n][k];
    if(ans!=-1)return ans;
    ans=0LL;
    (ans+=GetDP(n-1,k)*(((LL)n*(n-1LL)/2LL)*2LL%MOD))%=MOD;
    if(k>1)(ans+=GetDP(n-2,k-1)*(((LL)n*(n-1LL)/2LL)%MOD*(n-1LL)%MOD))%=MOD;
    return ans;
}
int N,K;
int main()
{
//    freopen("in.txt","r",stdin);
    for(int i=2;i<=100000;i++)for(int j=1;j<=50;j++)DP[i][j]=-1LL;
    DP[2][1]=1;
//    DP[4][2]=1*3*(4*3)/2*(2*1)/2;
    //DP[2k][k]=1*3*...*2k-1*k!/2^(k/2)
    for(int k=2;k<=50;k++)DP[2*k][k]=(DP[2*(k-1)][k-1]*(2LL*k-1LL)%MOD*((2LL*k*(2LL*k-1LL))/2LL)%MOD);
//    for(int i=1;i<=5;i++)printf("%lld ",DP[i*2][i]);puts("");
    int testcount;scanf("%d",&testcount);
    while(testcount--)
    {
        scanf("%d%d",&N,&K);
        static int kase=1;
        printf("Case %d: %lld\n",kase++,GetDP(N,K));
    }
    return 0;
}