HDU 5698——瞬间移动——————【逆元求组合数】

时间：2023-03-09 23:08:38
HDU 5698——瞬间移动——————【逆元求组合数】

　　　　　　　　瞬间移动

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 205    Accepted Submission(s): 109

Problem Description
有一个无限大的矩形，初始时你在左上角（即第一行第一列），每次你都可以选择一个右下方格子，并瞬移过去（如从下图中的红色格子能直接瞬移到蓝色格子），求到第n行第m列的格子有几种方案，答案对1000000007取模。
HDU 5698——瞬间移动——————【逆元求组合数】
Input
多组测试数据。

两个整数n,m(2≤n,m≤100000)

Output
一个整数表示答案
Sample Input
解题思路：比赛时候递推了一下，可以求出每个位置的方案数，以为是dp，后来就各种想不通怎么求。最开始看到这个题目的时候，有想组合，但是自己组合一向比较渣，所以就没细想。比赛完了看了一下别人的代码，才突然明白。想做出这个题目需要掌握：逆元求组合数， 快速幂。还有就是明白为什么要枚举1->min(n-2,m-2)。给我们一个坐标，我们可以得出可以移动到的区域即（n-2）*（m-2）。枚举要在这个区域停留几次，C(y,k)，表示从y列中选k列去停，C（x，k）表示从x行中选哪k行去停。所以乘积累加即为结果。
lucas定理可以求大组合数取模。
#include <iostream>

#include<algorithm>

#include<stdio.h>

#include<vector>

using namespace std;

typedef long long LL;

const int maxn = 1e5+200;

const int mod = 1e9+7;

#define mid (L+R)/2

#define lson rt*2,L,mid

#define rson mid+1,R

LL quick(LL x, LL n){

    if(n == 0)

        return 1;

    LL ret = 1;

    while(n){

        if(n&1)

            ret = (ret*x) % mod;

        n = n>>1;

        x = (x*x) % mod;

    }

    return ret;

}

LL fac[maxn], inv[maxn];

LL C(LL n, LL m){

    if(n == m) return 1;

    if(n < m) return 0;

    return (fac[n] * inv[n-m]) % mod * inv[m] % mod;

}

int main(){

    int n , m;

    fac[0] = 1;

    for(int i = 1; i <= maxn - 10; i++){

        fac[i] = (fac[i-1] * i) % mod;

    }

//    for(int i = 1; i <= 100100; i++){         //这种比较慢，可以有O(n)的递推

//        inv[i] = quick(fac[i] ,(LL)mod-2);

//    }

    inv[maxn-10] = quick(fac[maxn-10],mod-2);

    for(int i = maxn-11; i >= 1; i--){  //递推求解阶乘的逆元

        inv[i] = inv[i+1] * (i+1) % mod;

    }

    while(scanf("%d%d",&n,&m)!=EOF){

        if(n > m)

            swap(n,m);

        n--; m--;

        LL ans = 1;

        for(int i = 1; i < n; i++){

            ans = (ans + (C(n-1,i)*C(m-1,i)) % mod) % mod;

        }

        printf("%d\n",ans%mod);

    }

    return 0;

}

　　

相关文章