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

x和y分开考虑,在(1,1)到(n,m)之间可以选择走i步。就需要选i步对应的行C(n-2,i)及i步对应的列C(m-2,i)。相乘起来。 假设$mleq n$
$$sum_{i=1}^{m-2} C_{n-2}^icdot C_{m-2}^i=sum_{i=1}^{m-2} C_{n-2}^icdot 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=kcdot i+r equiv 0 pmod M$$
两边乘上$i^{-1}cdot r^{-1}$(如果M不是质数,r就可能为0)
$$egin{eqnarray} kcdot r^{-1}+i^{-1} &equiv& 0 &pmod M\
i^{-1} &equiv& -kcdot r^{-1} &pmod M\
i^{-1} &equiv& M-leftlfloorfrac{M}{i} ight floorcdot left(Mmod i ight)^{-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
",C(m+n-4,m-2));
}

  

原文地址:https://www.cnblogs.com/flipped/p/5701879.html