游客 注册 | 登录
中文 | En

2486 - J

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 128 MB

象 是国际象棋中的一种棋子，象的走法只可斜走，格数不限，但不可转向。
    白格的象只可以在白格出现，黑格的象只可以在黑格出现。
    现在给你一个n*n的棋盘，放置恰好k只象，且每只象不在其他象的攻击范围之内，输出方案数对(1e9+7)取余的值。

题目输入

多组数据，每组输入n,k (n<100,k<10000)

<br />

题目输出

输出方案数%1000000007。

输入/输出样例

输入格式

2 1
2 2
6 8

输出格式

4
4
12944

C++解答

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long LL;
#define mod 1000000007
#define N 101
int b[N],w[N];
int n,k;
LL R_b[N][N*N],R_w[N][N*N];
void cal(int c[],LL R[][N*N]){
    memset(R,0,sizeof(R));
    for(int i=0;i<=n;i++) R[i][0]=1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=c[i];j++)
            R[i][j]=(R[i-1][j]+R[i-1][j-1]*(c[i]-(j-1)))%mod;
}
int main(){
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    while(scanf("%d%d",&n,&k)!=EOF){
        if(n==0 && k==0) break;
        memset(b,0,sizeof(b)),memset(w,0,sizeof(w));
        memset(R_w,0,sizeof(R_w)),memset(R_b,0,sizeof(R_b));
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                if((i+j)&1) w[(i+j)>>1]++;
                else b[(i+j)>>1]++;
        sort(w+1,w+n),sort(b+1,b+n+1);
        cal(w,R_w),cal(b,R_b);
        LL ans=0;
        for(int i=0;i<=k;i++)
            ans=(ans+R_w[n-1][i]*R_b[n][k-i])%mod;
        printf("%lld\n",ans);
    }
    return 0;
}

Java解答

import java.math.*;
import java.util.*;
public class Main{
    public static void main(String args[]){
         Scanner in = new Scanner(System.in);
         while(in.hasNext()){
             int n=in.nextInt();
             int K=in.nextInt();
             int w[]=new int[n];
             int b[]=new int[n];
             int num_w=0,num_b=0;
             w[num_w++]=n;
             for(int i=n-2;i>=1;i-=2){
                 w[num_w++]=i;
                 w[num_w++]=i;
             }
             for(int i=n-1;i>=1;i-=2){
                 b[num_b++]=i;
                 b[num_b++]=i;
             }
             Arrays.sort(w,0,num_w);
             Arrays.sort(b,0,num_b);
             BigInteger[][] dp=new BigInteger[2][n+1];
             BigInteger[][] dq=new BigInteger[2][n+1];
             for(int i=0;i<2;i++){
                 for(int j=0;j<=n;j++){
                     dp[i][j]=BigInteger.ZERO;
                     dq[i][j]=BigInteger.ZERO;
                 }
             }
             dp[0][0]=dq[0][0]=BigInteger.ONE;
             int x=1,y=1;
             for(int i=0;i<num_w;i++){
                 for(int j=0;j<=i+1;j++){
                     dp[x][j]=dp[x^1][j];
                 }
                 for(int j=1;j<=i+1 && w[i]-(j-1)>=0;j++){
                     dp[x][j]=dp[x][j].add(dp[x^1][j-1].multiply(BigInteger.valueOf(w[i]-(j-1))));
                 }
                 x^=1;
             }
             x^=1;
             for(int i=0;i<num_b;i++){
                 for(int j=0;j<=i+1;j++){
                     dq[y][j]=dq[y^1][j];
                 }
                 for(int j=1;j<=i+1 && b[i]-(j-1)>=0;j++){
                     dq[y][j]=dq[y][j].add(dq[y^1][j-1].multiply(BigInteger.valueOf(b[i]-(j-1))));
                 }
                 y^=1;
             }
             y^=1;
             BigInteger ans=BigInteger.ZERO;
             for(int i=0;i<=num_w && i<=K;i++){
                 if(K-i<=num_b){
                    ans=ans.add(dp[x][i].multiply(dq[y][K-i]));
                 }
             }
             System.out.println(ans.mod(BigInteger.valueOf(1000000007)));
         }
    }
}
请先登陆