专栏首页饶文津的专栏【HDU 5698】瞬间移动(组合数,逆元)

【HDU 5698】瞬间移动(组合数,逆元)

m\leq n

$\sum_{i=1}^{m-2} C_{n-2}^i\cdot C_{m-2}^i=\sum_{i=1}^{m-2} C_{n-2}^i\cdot C_{m-2}^{m-2-i}=C_{n+m-4}^{m-2}

然后标程里求i的阶乘的逆是预处理的,主要这句:

f[i]=(M-M/i)\cdot f[M\%i]\%M

这里f即i的逆元,为什么可以这么求呢?

首先这里的M必须是质数。

M=k\cdot i+r \equiv 0 \pmod M

两边乘上(如果M不是质数,r就可能为0)

\begin{eqnarray} k\cdot r^{-1}+i^{-1} &\equiv& 0 &\pmod M\\i^{-1} &\equiv& -k\cdot r^{-1} &\pmod M\\i^{-1} &\equiv& M-\left\lfloor\frac{M}{i}\right\rfloor\cdot \left(M\bmod i\right)^{-1} &\pmod M \end{eqnarray}
#include<cstdio>
#define M 1000000007
#define N 200001
#define ll long long
ll fac[N]={1,1},inv[N]={1,1},f[N]={1,1};
int n,m;
ll C(ll a,ll b){
    return fac[a]*inv[b]%M*inv[a-b]%M;
}
int main(){
    for(int i=2;i<N;i++){
        fac[i]=fac[i-1]*i%M;
        f[i]=(M-M/i)*f[M%i]%M;
        inv[i]=inv[i-1]*f[i]%M;
    }
    while(~scanf("%d%d",&n,&m))
        printf("%lld\n",C(m+n-4,m-2));
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【Gym 100947E】Qwerty78 Trip(组合数取模/费马小定理)

    从(1,1)到(n,m),每次向右或向下走一步,,不能经过(x,y),求走的方案数取模。 可以经过(x,y)则相当于m+n步里面选n步必须向下走,方案数为

    饶文津
  • 【CodeForces 520E】Pluses everywhere

    n个数里插入k个+号,所有式子的和是多少(取模1000000007) (0 ≤ k < n ≤ 105)。

    饶文津
  • 【HDU - 4344】Mark the Rope(大整数分解)

    饶文津
  • 【Gym 100947E】Qwerty78 Trip(组合数取模/费马小定理)

    从(1,1)到(n,m),每次向右或向下走一步,,不能经过(x,y),求走的方案数取模。 可以经过(x,y)则相当于m+n步里面选n步必须向下走,方案数为

    饶文津
  • 2017"百度之星"程序设计大赛 - 资格赛【1001 Floyd求最小环 1002 歪解(并查集),1003 完全背包 1004 01背包 1005 打表找规律+卡特兰数】

    度度熊保护村庄 Accepts: 13 Submissions: 488 Time Limit: 2000/1000 MS (Java/Others)...

    Angel_Kitty
  • Lucas(卢卡斯定理)模板

             Lucas用来求C(n,m)%p的值,适用于解决n,m较大,p(一定为素数)小于1e6的情况。

    Ch_Zaqdt
  • 简单并查集讲解

    但是这里存在一个很显然的问题。对于一条链来说,我们查询叶子结点的祖先的时候会把所有结点都遍历一遍,为了避免这种情况,我们可以有两种策略对其优化

    ACM算法日常
  • 实现文本自动分类的基础----Term频率计算方法

        据说如今互联网上的文档每天以100万的数量增长,这么大的增长量使得Google可能需要1个月甚至更长的时间才能光顾你的网站一次。所以如果你今天对你的网页...

    田春峰-JCJC错别字检测
  • LeetCode 93 | 生成所有有效的IP地址

    今天是LeetCode专题的第59篇文章,我们一起来看看LeetCode第93题,有效ip地址(Restore IP Addresses)。

    TechFlow-承志
  • Linux centos下设置定时备份任务的方法步骤

    砸漏

扫码关注云+社区

领取腾讯云代金券