【zzuliOJ】1894 - 985的方格难题（组合数学）

FishWang

发布于 2025-08-26 15:05:49

9500

代码可运行

运行总次数：0

代码可运行

点击打开题目

1894: 985的方格难题

Time Limit: 1 Sec Memory Limit: 128 MB Submit: 332 Solved: 63 Submit Status Web Board

Description

985走入了一个n * n的方格地图，他已经知道其中有一个格子是坏的。现在他要从(1, 1)走到(n, n)，每次只可以向下或者向右走一步，问他能否到达（n，n）。若不能到达输出-1，反之输出到达（n，n）的方案数。

Input

第一行输入一个整数t，代表有t组测试数据。

每组数据第一行输入三个整数n，x，y，分别代表方格地图的大小以及坏掉格子的位置。

注：1 <= t <= 20，1 <= n <= 30，1 <= x，y <= n。

Output

若可以到达（n，n）则输出方案数对1e9 + 7取余的结果，反之输出-1。

Sample Input

2 1 2

2 2 2

Sample Output

-1

HINT

Source

hpu

搞懂组合数学在这里怎么用，再学会打表就行了，记得用longlong。

代码如下：（比赛的时候是用java拍的抢首A的，拍完发现比赛的时候不支持java提交）

java代码：

import java.math.BigDecimal;
import java.util.Scanner;

public class Main
{
	public static void main(String[] args)
	{
		Scanner sc = new Scanner(System.in);
		BigDecimal c[][] = new BigDecimal [66][66];
		for (int i = 1 ; i <= 60 ; i++)
		{
		    c[i][0] = new BigDecimal(1);
		    c[i][i] = new BigDecimal(1);
		}
		for (int i = 1 ; i <= 60 ; i++)
		{
		    for (int j = 1 ; j < i ; j++)
		    {
		        c[i][j] = c[i-1][j].add(c[i-1][j-1]);
		    }
		}
		int u = sc.nextInt();
		while (u != 0)
		{
		    u--;
		    int n = sc.nextInt();
		    int x = sc.nextInt();
		    int y = sc.nextInt();
		    if ((x == n && y == n) || (x == 1 && y == 1))
		    {
		        System.out.println(-1);
		        continue;
		    }
		    BigDecimal ans = new BigDecimal(0);
		    int t = n-1;
		    BigDecimal MOD = new BigDecimal(1000000007);
		    BigDecimal neg = new BigDecimal(-1);
		    ans = ans.add(c[t*2][t]);
		    ans = ans.add(c[x-1+y-1][x-1].multiply(c[n-x+n-y][n-x]).multiply(neg));
		    ans = ans.remainder(MOD);
		    System.out.println(ans);
		}
	}
}

C++代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define CLR(a,b) memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
long long MOD = 1000000007;
long long c[66][66];
void C()
{
    for (int i = 0 ; i <= 60 ; i++)
        c[i][0] = c[i][i] = 1;
    for (int i = 2 ; i <= 60 ; i++)
    {
        for (int j = 1 ; j < i ; j++)
            c[i][j] = (c[i-1][j] + c[i-1][j-1]) % MOD;
    }
}
int main()
{
    int u;
    int n;
    int x,y;
    C();
    scanf ("%d",&u);
    while (u--)
    {
        scanf ("%d %d %d",&n,&x,&y);
        if (x == n && y == n)
        {
            printf ("-1\n");
            continue;
        }
        else if (x == 1 && y == 1)
        {
            printf ("-1\n");
            continue;
        }
        long long ans;
        int t = n-1;
        ans = c[t*2][t];
        ans -= c[x-1+y-1][x-1] * c[n-x+n-y][n-x];
        ans = (ans % MOD + MOD) % MOD;
        printf ("%lld\n",ans);
    }
    return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-08-26，如有侵权请联系 cloudcommunity@tencent.com 删除

bigdecimal