51nod1119 机器人走方格组合数学

﹏ヽ暗。殇╰゛Y 2022-08-21 14:49 125阅读 0赞

M \* N的方格，一个机器人从左上走到右下，只能向右或向下走。有多少种不同的走法？由于方法数量可能很大，只需要输出Mod 10^9 + 7的结果。

题目本身很简单，就是一个初中都推倒过的理论，只能向下或者向右的话，那么可能的路径一共有C（n+m,n）种。很好理解的这里就不说明了。现在我们要解决的是，当n和m都比较大的时候怎么讲结果计算出来。

![Image 1][]

![Image 1][]

#include <cmath>
    #include <iostream>
    #include <cstring>
    #include "minmax.h"
    #include <cstdio>
    
    using namespace std ;
    
    #define LL long long
    #define p 1000000007
    
    LL n, m;
    
    LL quick_mod(LL a, LL b)
    {
    	LL ans = 1;
    	a %= p;
    	while (b)
    	{
    		if (b & 1)
    		{
    			ans = ans * a % p;
    			b--;
    		}
    		b >>= 1;
    		a = a * a % p;
    	}
    	return ans;
    }
    
    LL C(LL n, LL m)
    {
    	if (m > n) return 0;
    	LL ans = 1;
    	for (int i = 1; i <= m; i++)
    	{
    		LL a = (n + i - m) % p;
    		LL b = i % p;
    		ans = ans * (a * quick_mod(b, p - 2) % p) % p;
    	}
    	return ans;
    }
    
    LL Lucas(LL n, LL m)
    {
    	if (m == 0) return 1;
    	return C(n % p, m % p) * Lucas(n / p, m / p) % p;
    }
    
    int main()
    {
    	while (cin>>n>>m)
    	{
    		LL a = n + m - 2;
    		LL b = min(n, m) - 1;
    		printf("%I64d\n", Lucas(a,b));
    	}
    	return 0;
    }

[Image 1]:

发表评论取消回复

表情：

评论列表（有 0 条评论，125人围观）

还没有评论，来说两句吧...

相关阅读

相关（每日一练c++）CC182 机器人走方格II

前言 C++是一种计算机高级程序设计语言，由C语言扩展升级而产生，最早于1979年由本贾尼·斯特劳斯特卢普在AT&T贝尔工作室研发。 C++既可以进行C语言的过程化

偏执的太偏执、/ 2023年10月04日 18:03/ 0 赞/ 17 阅读

相关 (动态规划问题)机器人走方格

有一个XxY的网格，一个机器人只能走格点且只能向右或向下走，要从左上角走到右下角。请设计一个算法，计算机器人有多少种走法。给定两个正整数int x,int y，请返回机器人的

迷南。/ 2022年09月28日 11:58/ 0 赞/ 139 阅读

相关 51nod1119 机器人走方格组合数学

M \ N的方格，一个机器人从左上走到右下，只能向右或向下走。有多少种不同的走法？由于方法数量可能很大，只需要输出Mod 10^9 + 7的结果。题目本身很简单，

﹏ヽ暗。殇╰゛Y/ 2022年08月21日 14:49/ 0 赞/ 126 阅读

相关 51nod1070 博弈

有一堆石子共有N个。A B两个人轮流拿，A先拿。每次拿的数量最少1个，最多不超过对手上一次拿的数量的2倍（A第1次拿时要求不能全拿走）。拿到最后1颗石子的人获胜。假设A B都非

「爱情、让人受尽委屈。」/ 2022年08月21日 13:39/ 0 赞/ 141 阅读

相关 51nod 1043

题意：求在2\n位的数字中，前n位的和等于后n位的和的个数，比喻n=1的时候，11,22,33...99等数字都是的，还有1102，2121等都是满足要求的数字。n<=10

灰太狼/ 2022年08月21日 03:14/ 0 赞/ 180 阅读

相关 51nod-加农炮

一个长度为M的正整数数组A，表示从左向右的地形高度。测试一种加农炮，炮弹平行于地面从左向右飞行，高度为H，如果某处地形的高度大于等于炮弹飞行的高度H（A\[i\] >= H），

男娘i/ 2022年06月17日 14:08/ 0 赞/ 172 阅读

相关机器人走方格

M \ N的方格，一个机器人从左上走到右下，只能向右或向下走。有多少种不同的走法？由于方法数量可能很大，只需要输出Mod 10^9 + 7的结果。 Input 第1行，2个

叁歲伎倆/ 2022年06月12日 10:43/ 0 赞/ 126 阅读

相关 51nod-1770

为该问题添加一个话题隐藏话题 [1770 数数字][1770] 基准时间限制：1 秒空间限制：262144 KB 分值: 20 [难度：3级算法题][3] ![s

小灰灰/ 2022年05月28日 12:51/ 0 赞/ 153 阅读

相关 51nod--1284

[1284 2 3 5 7的倍数][1284_2_3_5_7] ![ok.png][] 基准时间限制：1 秒空间限制：131072 KB 分值: 5 [难度：1级算法题][

分手后的思念是犯贱/ 2022年05月27日 11:22/ 0 赞/ 155 阅读

相关机器人走方格

有一个X\Y的网格，一个机器人只能走格点且只能向右或向下走，要从左上角走到右下角。请设计一个算法，计算机器人有多少种走法。给定两个正整数int x,int y，请返回机器人

拼搏现实的明天。/ 2021年09月28日 19:48/ 0 赞/ 282 阅读