【题解】牛牛走方格

题意

从一个的矩形格子中，从走到，只能向上或者向左向右走，且走过的地方不能再走，问有多少条不同的路径。

题解

直接上来先写个dfs找找规律

//当n=3，然后m变化时有如下规律
3 2
4
3 3
9
3 4
16
3 5
25
3 6
36
3 7
49
3 8
64
3 9
81
3 10
100

这里就可以发现答案是了，那么我们再继续打别的情况的表看看

//当n=4，m变化时有如下规律
4 2
8
4 3
27
4 4
64
4 5
125
4 6
216
4 7
343

明显的发现答案变成了
所以不难推测最终的答案就是，那么我们使用快速幂就可以求解了。

复杂度

时间复杂度为
空间复杂度为

代码

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
long long quickmod(long long a,long long b)
{
    long long ans=1;
    while(b>0)
    {
        if(b%2==1)
            ans=ans*a%mod;
        b=b/2;
        a=a*a%mod;
    }
    return ans;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        printf("%lld\n",quickmod(m,n-1));
    }
    return 0;
}