本文共 1430 字，大约阅读时间需要 4 分钟。

1120 机器人走方格 V3

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

输入

输入一个数N(2 <= N <= 10^9)。

输出

输出走法的数量 Mod 10007。

输入样例

4

输出样例

10

解惑

lucas 定理是用来求 c(n,m) mod p

代码实现

总方案数：

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #define ll long longusing namespace std;const int mod = 10007;ll QuickPow(ll x, ll N) { ll res = x % mod; ll ans = 1; while (N) { if (N & 1) { ans = ans * res % mod; } res = res * res % mod; N = N / 2; } return ans % mod;}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) % mod; ll b = i % mod; ans = ans * (a * QuickPow(b, mod - 2) % mod) % mod; } return ans;}ll lucas(ll a, ll b) { if (b == 0) { return 1; } return C(a % mod, b % mod) * lucas(a / mod, b / mod) % mod;}int main() { ll n; scanf("%lld", &n); n--; printf("%lld\n", ((lucas(2 * n, n) - lucas(2 * n, n - 1) + mod) % mod) * 2 % mod);}
          
         
        
       
      
     
    
   

转载地址：https://blog.csdn.net/weixin_43820352/article/details/108303406 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！