UVA10237 Bishops

UVa

Luogu

Vjudge

分析

把棋盘旋转 $45^\circ$ ,然后黑白染色:

黑白格不会相互影响,所以我们现在只考虑黑格。

行的顺序是不影响答案的,所以我们排成这样:

设第 $i$ 行有 $l_i$ 个黑格,$f_{i,j}$ 表示前 $i$ 行黑格中放 $j$ 个的方案数。

容易得到

$$ f_{i,j}=f_{i-1,j}+(l_i-j+1)f_{i-1,j-1} $$

边界是 $f_{i,0}=1$ 。

再设 $g_{i,j}$ 表示前 $i$ 行白格中放 $j$ 个的方案数。这个和上面差不多。

那么 $(n,k)$ 的答案就是

$$ \sum_{i=0}^kf_{n,i}\times g_{n-1,k-i} $$

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
#define int long long
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100+10;

int n,k;
int f[N][N],g[N][N];

signed main() {
    for (re int i=f[0][0]=1;i<=30;++i) {
        int l=i-!(i&1);
        for (re int j=f[i][0]=1;j<=i;++j)
            f[i][j]=f[i-1][j]+(l-j+1)*f[i-1][j-1];
    }
    for (re int i=g[0][0]=1;i<=30;++i) {
        int l=i+(i&1);
        for (re int j=g[i][0]=1;j<=i;++j)
            g[i][j]=g[i-1][j]+(l-j+1)*g[i-1][j-1];
    }
    while (n=read()) { k=read();
        if (k>2*n-1) { puts("0"); continue; }
        int ans=0;
        for (re int i=0;i<=k;++i)
            ans+=f[n][i]*g[n-1][k-i];
        printf("%lld\n",ans);
    }
    return 0;
}
最后修改:2019 年 09 月 27 日 01 : 49 PM

发表评论