HDU 5698 大组合数取模(逆元)

瞬间移动

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

Problem Description

有一个无限大的矩形,初始时你在左上角(即第一行第一列),每次你都可以选择一个右下方格子,并瞬移过去(如从下图中的红色格子能直接瞬移到蓝色格子),求到第n行第m列的格子有几种方案,答案对1000000007取模。

Input

多组测试数据。

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

Output

一个整数表示答案

Sample Input

4 5

Sample Output

10

还是搞不懂那个递推式怎么正确的推出来的,我是自己手推发现像杨辉三角也就是组合数,多试几次得出规律,

对于n,m,ans=C(n+m-4,m-2),现在的问题就是n最大10w,C(N,M)=N!/(M!*(N-M)!),由于除法再加上模大质数,想到了逆元

这里有一个更方便推得式子 C(N,M)%MOD={(N-M+1)/(M)*C(N,M-1)}%MOD=(N-M+1)*inv[M]*C(N,M-1)%MOD;

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define MOD 1000000007
LL inv[100005]={1,1};
int main()
{
    int N,i,M,j,k;
    for(i=2;i<=100000;++i) inv[i]=(MOD-MOD/i)*inv[MOD%i]%MOD;
    while(scanf("%d%d",&N,&M)==2) {
        int n=N+M-4,m=M-2;
        LL ans=1;
        for(i=1;i<=m;++i){
            ans=(n-i+1)*inv[i]%MOD*ans%MOD;
        }
        printf("%lld\n",ans);
    }
    return 0;
}

时间: 07-17

HDU 5698 大组合数取模(逆元)的相关文章

大组合数取模之lucas定理模板,1&lt;=n&lt;=m&lt;=1e9,1&lt;p&lt;=1e6,p必须为素数

typedef long long ll; /********************************** 大组合数取模之lucas定理模板,1<=n<=m<=1e9,1<p<=1e6,p必须为素数 输入:C(n,m)%p 调用lucas(n,m,p) 复杂度:min(m,p)*log(m) ***********************************/ //ax + by = gcd(a,b) //传入固定值a,b.放回 d=gcd(a,b), x , y

排列组合+组合数取模 HDU 5894

1 // 排列组合+组合数取模 HDU 5894 2 // 题意:n个座位不同,m个人去坐(人是一样的),每个人之间至少相隔k个座位问方案数 3 // 思路: 4 // 定好m个人 相邻人之间k个座位 剩下就剩n-(m+1)*k个座位 5 // 剩下座位去插m个不同的盒子==就等价n个相同的球放m个不同的盒子 6 // 然后组合数出来了 7 // 乘n的话是枚举座位,除m是去掉枚举第一个座位的时候,剩下人相邻的座位相对不变的情况 8 9 #include <iostream> 10 #incl

hdu 3037 Saving Beans 组合数取模模板题。。

Saving Beans Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 2707    Accepted Submission(s): 1014 Problem Description Although winter is far away, squirrels have to work day and night to save b

组合数取模Lucas定理及快速幂取模

组合数取模就是求的值,根据,和的取值范围不同,采取的方法也不一样. 下面,我们来看常见的两种取值情况(m.n在64位整数型范围内) (1)  , 此时较简单,在O(n2)可承受的情况下组合数的计算可以直接用杨辉三角递推,边做加法边取模. (2) ,   ,并且是素数 本文针对该取值范围较大又不太大的情况(2)进行讨论. 这个问题可以使用Lucas定理,定理描述: 其中 这样将组合数的求解分解为小问题的乘积,下面考虑计算C(ni, mi) %p. 已知C(n, m) mod p = n!/(m!(

组合数取模终极版

以前讲述过很多组合数取模问题,详见:http://blog.csdn.net/acdreamers/article/details/8037918 今天,我们继续学习一些稍有难度的组合数取模问题,比如大组合数对合数取模,求大组合数的最后位数字等等. 首先来看组合数对合数取模问题 问题:求的值,其中和,并且是合数. 分析:先把素因子分解,然后转化为求,这里为素数,然后用CRT合并.所以现在重点来研究 如何求的值.这个问题AekdyCoin大神已经详细讲述了,如下链接     链接:http://h

toj 4111 组合数取模 暴力分解

题目大意:组合数取模,n和m并不算大,p比较大且是合数. 思路:暴力分解+快速幂 注:暴力也是有区别的,分解质因数时可以用以下work函数,写的非常巧妙,摘录自互联网. 1 #include <iostream> 2 #include <cstring> 3 using namespace std; 4 5 typedef long long ll; 6 const ll mod = 1ll << 32; 7 const int N = 1000001; 8 const

[BZOJ 3129] [Sdoi2013] 方程 【容斥+组合数取模+中国剩余定理】

题目链接:BZOJ - 3129 题目分析 使用隔板法的思想,如果没有任何限制条件,那么方案数就是 C(m - 1, n - 1). 如果有一个限制条件是 xi >= Ai ,那么我们就可以将 m 减去 Ai - 1 ,相当于将这一部分固定分给 xi,就转化为无限制的情况了. 如果有一些限制条件是 xi <= Ai 呢?直接来求就不行了,但是注意到这样的限制不超过 8 个,我们可以使用容斥原理来求. 考虑容斥:考虑哪些限制条件被违反了,也就是说,有哪些限制为 xi <= Ai 却是 xi

逆元 - 组合数取模

现在目标是求$C_n^m\%p$,p为素数(经典p=1e9+7) 虽然有$C_n^m=\frac{n!}{m!(n-m)!}$,但由于取模的性质对于除法不适用,所以$C_n^m\%p$≠$( \frac{n!\%p}{m!\%p*(n-m)!\%p} )\%p$ 所以需要把"除法"转换成"乘法",才能借助取模的性质在不爆long long的情况下计算组合数.这时候就需要用到"逆元"! 逆元:对于a和p,若a*b%p≡1,则称b为a%p的逆元. 那

组合数取模(转载)

本文转自:http://blog.csdn.net/skywalkert/article/details/52553048 0. 写在前面 在程序设计中,可能会碰到多种类型的计数问题,其中不少涉及到组合数的计算,所以笔者写下这么一篇文章,期望能解决一些常规的组合数求模问题.以下部分内容改编自AekdyCoin的<组合数求模>,而且为了感谢他对(懵懂的)笔者的启发,这篇文章的标题与其文章相同.另外,感谢Picks将多项式运算的技巧在中国进行推广,感谢51nod提供了许多有趣的数论题目,感谢fot

大整数取模运算出现运算结果负数的解决方案

首先我们看个例子 <?php echo 12121212121 % 1000000; //结果为 -689767 //实际应该为12121 ?> 这里的取模运算(取余数)出现了BUG.那么需要声明一下,负数也是可以取模操作的,并不是出现负数就是不对的我们应该把这种长整数类型看成float型数据进行处理介绍一个函数float fmod ( float $x , float $y )返回除法的浮点数余数通过这个函数的运算,就可以得到原本想要的余数结果 <?php $a = floatval(