首页 > 试题广场 >

牛牛走方格

[编程题]牛牛走方格
  • 热度指数：137 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
牛牛进入了方格世界，方格世界由个方格构成的高为宽为的矩形，牛牛所在的方格为，而方格世界的出口在。在方格世界中，牛牛只能向上走或者向左或向右走，而且牛牛走过的方格不能再次进入。牛牛想知道他有多少种走出方格世界的路径，答案可能很大请对取模。

输入描述:
第一行为一个，表示有组数据。
接下来有行，每行有两个数字和。




输出描述:
输出为行，每行一个数字表示答案。
示例1

输入

2
2 2
3 3

输出

2
9
算法知识视频讲解
添加回答
coder121388头像 coder121388
const readline = require("readline")
const rl=readline.createInterface({
    input:process.stdin,
    output:process.stdout
})
var num=0;
function fastPow(m,n,mod=1000000007){//这是错误的小的数的做法
    if(n==0){
        return 1;
    }
    else if(n%2==0){
        let a = fastPow(m,n/2);
        return (a*a)%mod;
    }
    else if(n%2==1){
        return (m*fastPow(m,n-1))%mod;
    }

}
const bPowPlus = function (m, n, mod=1000000007n) {
    // 2^13 => 13: 1101，13 = 2^3 + 2^2 + 2^1 = 8 + 4 + 1
    // 2^13 = 2^8 * 2^4 * 2^1。
    var res = 1n;
    bm=BigInt(m);
    bn=BigInt(n);
    while (bn > 0n) {
        if (bn % 2n==1n) { // 当为b%2 == 1时
            res = (res * bm)% mod;
        }
        bm = (bm*bm)% mod;
        bn =bn/2n;
    }
    return Number(res);
}
rl.on("line",function(line){
    if(num==0){
       var numb = Number(line);
       num++;
    }
    else{
        var [n,m] = line.split(" ");
        //var res = Math.pow(m, n-1);
        //res=res%1000000007;
        n=Number(n);
        m=Number(m);
        var res = bPowPlus(m,n-1);
        console.log(res);
    }
})

//但是为什么输入集有足足1000000个
编辑于 2022-03-21 15:50:56 回复(0)
4fbd81e头像 4fbd81e 
//注意快速幂里a=a*a%mod
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mod 1000000007

//非递归快速幂
ll qpow(ll a, ll n){
    ll ans = 1;
    while(n){
        if(n&1)        //如果n的当前末位为1
            ans =(ans%mod)*(a%mod)%mod;  //ans乘上当前的a
        a=a*a%mod;        //a自乘
        n >>= 1;       //n往右移一位
    }
    return (ans+mod)%mod;
}

int main(){
    ll t;
    ll n,m;
    scanf("%lld",&t);
    while(t--){
        scanf("%lld%lld",&n,&m);
        printf("%lld\n",qpow(m,n-1));
    }
    return 0;
}

发表于 2021-05-11 23:34:42 回复(0)
ASusie头像 ASusie
为啥我画图画出来3*3的方格有12种走法啊？题目却说只有9种...
发表于 2021-03-19 12:44:03 回复(1)
Python
苏梓亭头像 苏梓亭 
class Solution: def mergeTwoLists(self , n , m ):
        t=1  for i in range(n-1):
            t*=(m) return t
发表于 2021-03-18 15:40:34 回复(0)
提交观点

问题信息

贝壳找房 前端工程师 2021
来自：贝壳找房2023届校招...
上传者：小小
难度：
4条回答 2095浏览

热门推荐

通过挑战的用户

相关试题

牛牛走方格

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号