51nod 1120 机器人走方格V3【卡特兰数】【卢卡斯定理】

50 阅读 0 评论 33 点赞

我是靠谱客的博主淡定烧鹅，最近开发中收集的这篇文章主要介绍51nod 1120 机器人走方格V3【卡特兰数】【卢卡斯定理】，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Description

N * N的方格，从左上到右下画一条线。一个机器人从左上走到右下，只能向右或向下走。并要求只能在这条线的上面或下面走，不能穿越这条线，有多少种不同的走法？由于方法数量可能很大，只需要输出Mod 10007的结果。

题解

答案就是 $H(N-1)*2%tt$ 。

所以就是一个求大组合数模一个质数的题目，可以用卢卡斯定理

(x y) = (x m o d p y m o d p) \times ⎛ ⎝ ⌊ x p ⌋ ⌊ y p ⌋ ⎞ ⎠

${xchoose y}={x mod pchoose y mod p}times {lfloor{xover p}rfloorchoose lfloor{yover p}rfloor}$

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
#define tt 10007
using namespace std;
int n,p,f[tt+6],inv[tt+6];
int power(int x,int y){
    int w=x,sum=1;
    while(y){
        if(y&1)sum=(LL)sum*w%tt;
        y>>=1;w=(LL)w*w%tt;
    }
    return sum;
}
int C(int n,int m){
    if(n<tt&&m<tt)return (LL)f[n]*inv[m]%tt*inv[n-m]%tt;
    return (LL)C(n/tt,m/tt)*C(n%tt,m%tt)%tt;
}
int main(){
    freopen("robot.in","r",stdin);
    freopen("robot.out","w",stdout);
    scanf("%d",&n);n--;
    f[0]=1;
    for(int i=1;i<tt;i++)f[i]=(LL)f[i-1]*i%tt;
    inv[tt-1]=power(f[tt-1],tt-2);
    for(int i=tt-2;i>=0;i--)inv[i]=(LL)(inv[i+1]*(i+1))%tt;
    p=power(n+1,tt-2);
    printf("%lldn",(LL)C(n*2,n)*p%tt*2%tt);
}