51nod 1120 机器人走方格 V3 卡特兰数 lucas定理

时间:2022-12-23 19:26:56

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

 
Input
输入一个数N(2 <= N <= 10^9)。
Output
输出走法的数量 Mod 10007。
Input示例
4
Output示例
10

明显是一道卡特兰数,推出ans = C(2*n-2,n-1) * 2 / n % MOD
先让n--,ans = C(2*n,n) * 2 / (n+1) % MOD 这样公式看起来好看些 由于 n <= 10^9,但是 MOD = 10007,所以求ans需要用到lucas定理
  //File Name: nod1120.cpp
//Author: long
//Mail: 736726758@qq.com
//Created Time: 2016年05月27日 星期五 15时46分58秒 #include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream> #define LL long long using namespace std; const int MOD = ; LL jie[MOD]; LL qp(LL x,LL y){
LL res = ;
while(y){
if(y & ) res = res * x % MOD;
x = x * x % MOD;
y >>= ;
}
return res;
} void init(){
jie[] = ;
for(int i=;i<MOD;i++)
jie[i] = jie[i-] * i % MOD;
} LL get_c(int x,int y){
if(y == || y == x) return ;
return jie[x] * qp(jie[y] * jie[x-y] % MOD,MOD - ) % MOD;
} LL lucas(LL x,LL y){
LL ans = ;
int u,v;
while(x > || y > ){
u = x % MOD;
v = y % MOD;
ans = ans * get_c(u,v) % MOD;
x /= MOD;
y /= MOD;
}
return ans;
} int main(){
init();
int n;
while(~scanf("%d",&n)){
n--;
printf("%d\n",(int)lucas(*n,n) * qp(n+,MOD-) * % MOD);
}
return ;
}

51nod 1120 机器人走方格 V3 卡特兰数 lucas定理的更多相关文章

  1. 51nod 1120 机器人走方格V3

    1120 机器人走方格 V3  基准时间限制:1 秒 空间限制:131072 KB 分值: 80 难度:5级算法题  收藏  关注 N * N的方格,从左上到右下画一条线.一个机器人从左上走到右下,只 ...

  2. 51nod 1120 机器人走方格 V3 【卡特兰数&plus;卢卡斯定理&plus;组合数】

    -我并不知道为什么事卡特兰数,反正用dp打的表就是卡特兰数,因为是两个三角所以再乘个2 卡特兰数使用\( h(n)=\frac{C_{2n}^{n}}{n+1} \)因为范围比较大所以组合数部分用卢卡 ...

  3. 51Nod 机器人走方格 V3 —— 卡特兰数、Lucas定理

    题目链接:http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1120 题解: 1.看到这种题,马上就想到了卡特兰数.但卡特兰数 ...

  4. 51nod 1120 机器人走方格 V3

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

  5. 1120 机器人走方格 V3

    1120 机器人走方格 V3 基准时间限制:1 秒 空间限制:131072 KB N * N的方格,从左上到右下画一条线.一个机器人从左上走到右下,只能向右或向下走.并要求只能在这条线的上面或下面走, ...

  6. 1120 机器人走方格 V3(组合数)

    题目实际上是求catalan数的,Catalan[n] = C(2*n,n) / (n+1) = C(2*n,n) % mod * inv[n+1],inv[n+1]为n+1的逆元,根据费马小定理,可 ...

  7. 51nod1120 机器人走方格 V3

    跟括号序列是一样的,将向右走看成是左括号向左走看成是右括号就可以了.那么就是卡特兰数了.然后由于n和m太大所以用了lucas定理 //跟括号序列是一样的,将向右走看成是左括号向左走看成是右括号就可以了 ...

  8. 机器人走方格 V3

    1120 . 机器人走方格 V3   基准时间限制:1 秒 空间限制:65536 KB 分值: 160 N * N的方格,从左上到右下画一条线.一个机器人从左上走到右下,只能向右或向下走.并要求只能在 ...

  9. 51nod 1118 机器人走方格 解题思路:动态规划 &amp&semi; 1119 机器人走方格 V2 解题思路:根据杨辉三角转化问题为组合数和求逆元问题

    51nod 1118 机器人走方格: 思路:这是一道简单题,很容易就看出用动态规划扫一遍就可以得到结果, 时间复杂度O(m*n).运算量1000*1000 = 1000000,很明显不会超时. 递推式 ...

随机推荐

  1. React Native之生命周期

    React Native生命周期主要分为三大阶段:实例化阶段(图中上框部分),存在阶段(图中左框部分),销毁阶段(图中右框部分). 如图: 下面简单讲解一下三大阶段中各自的函数: 实例化阶段: 在日常 ...

  2. linux BASH shell设置字体与背景颜色

    linux BASH shell下设置字体及背景颜色的方法. BASH shell下设置字体及背景颜色  echo -e "\e[31mtest\e[41m"  \e[30m 将字 ...

  3. 《编写高质量代码-Web前端开发修改之道》笔记--第二章 团队合作

    本章内容: 揭秘前端开发工程师 欲精一行,必先通十行 增加代码的可读性--注释 提高重用性--公共组件和私有组件的维护 冗余和精简的矛盾--选择集中还是选择分散 磨刀不误砍柴工--前期的构思很重要 制 ...

  4. 如何:在 StackPanel 和 DockPanel 之间进行选择

    虽然可以使用 DockPanel 或 StackPanel 来堆叠子元素,但这两个控件并不总是会产生相同的结果. 例如,子元素的放置顺序可能会影响 DockPanel 中子元素的大小,但不会影响 St ...

  5. Sencha Architect 激活方法

     Sencha Architect 2是ExtJS和Sencha Touch的官方可视化IDE工具.最新版本是2.2,说是破解,其实是修改License来实现无限试用而已. 1.先下载安装官方软件,大 ...

  6. Jmeter性能测试 及压测入门

    Jmeter是一个非常好用的压力测试工具.  Jmeter用来做轻量级的压力测试,非常合适,只需要十几分钟,就能把压力测试需要的脚本写好. 为什么要建立线程组?原因很简单,因为我们要模拟多个线程(用户 ...

  7. java-9 异常处理

    1.异常处理的基础知识 异常是程序中的一些错误,但并不是所有的错误都是异常,并且错误有时候是可以避免的. 比如说,你的代码少了一个分号,那么运行出来结果是提示是错误 java.lang.Error:如 ...

  8. 201521123075 《Java程序设计》第10周学习总结

    1. 本周学习总结 2. 书面作业 本次PTA作业题集异常.多线程 1.finally 题目4-2 1.1 截图你的提交结果(出现学号) 1.2 4-2中finally中捕获异常需要注意什么? fin ...

  9. &lbrack;Python Study Notes&rsqb;with的使用

    在 Python 2.5 中, with 关键字被加入.它将常用的 try ... except ... finally ... 模式很方便的被复用.看一个最经典的例子: with open('fil ...

  10. ASP&period;NET 通过配置hiddenSegment禁止目录下资源通过Url形式访问

    根据默认的ASP.NET配置,App_Data下的资源是禁止通过Url形式直接访问的,在实际开发中,可能也会有这样的需求,比如某些是系统资源目录,该目录下的资源也需要像App_Data目录一样禁止访问 ...