Sgu/220

玩過國際象棋的人都知道,處於不同顏色的格子中的象永遠不可能相互攻擊到,所以可以將棋盤按照黑白色一分為二,并將兩部份旋轉45度角,然後對於每一部份,設f[i][j]為前i行總共放了j個象的放法數,則轉移方程為:dp[i][j]=dp[i-1][j]+dp[i-1][j-1]*(該行的格子數-j+1);最後統計一下即可.

另外注意該題答案需要用int64(long long)存儲.

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define maxn 11
long long f1[maxn][maxn*maxn],f2[maxn][maxn*maxn];
int l1[maxn],l2[maxn];
long long ans;
int n,bishop;
int main(){
  scanf("%d%d",&n,&bishop);
  for(int i=1,j=n;i<=j;++i,--j)
    l1[j]=l1[i]=(i<<1)-1;
  for(int i=1,j=n-1;i<=j;++i,--j)
    l2[j]=l2[i]=(i<<1);
  sort(&l1[1],&l1[n+1]),sort(&l2[1],&l2[n]);
  for(int i=0;i<=n;i++)
    f1[i][0]=f2[i][0]=1;
  for(int i=1;i<=n;i++)
    for(int j=1;j<=bishop;j++){
      f1[i][j]=f1[i-1][j];
      if(l1[i]+1>=j)
        f1[i][j]+=f1[i-1][j-1]*(l1[i]-j+1);
    }
  for(int i=1;i<n;i++)
    for(int j=1;j<=bishop;j++){
      f2[i][j]=f2[i-1][j];
      if(l2[i]+1>=j)
        f2[i][j]+=f2[i-1][j-1]*(l2[i]-j+1);
    }
  ans=0;
  for(int i=0;i<=bishop;i++)
    ans+=f1[n][i]*f2[n-1][bishop-i];
  printf("%I64d\n",ans);
  return 0;
}