【HDU 5698】瞬间移动

【题目链接】

点击打开链接

【算法】

用f[i][j]表示走到(i,j)这个位置有多少种方案，因为走到(i,j)这个位置，上一步一定在它左上角的矩形中，所以，

f(i,j) = sigma( f(x,y) ) ( (x,y)在左上角的矩形中）

我们尝试将它画出来，发现是斜着的杨辉三角

然后，通过找规律，我们发现 : f(n,m) = C(n+m-4,n-2)

求C函数的值，这里有一种方法：

C(n,r) mod P = (n! / (n - r)! / r!) mod P

= (n!) mod P * inv( (n - r)! ) mod P * inv( r! ) mod P（其中,inv表示乘法逆元）

考虑预处理阶乘和阶乘逆元

阶乘很容易求，那么，阶乘逆元怎么求呢？

这里有一种线性求阶乘逆元的方法 ( 如果我们要求 inv( n! ) ) ：

inv(n ! ) = inv( (n - 1)! n )

= inv( (n - 1)! ) inv( n )

所以 inv( (n - 1)! ) = inv( n ! ) * inv( inv( n ) )

= inv( n! ) * n

有了这个式子，我们便可以在线性时间内求出所有的阶乘逆元

这一题，我们只要预处理阶乘和阶乘逆元，然后，O(1)回答询问，即可

【代码】

#include<bits/stdc++.h>

using namespace std;

#define MAXN 200010

const long long P = ;

long long n,m;

long long fac[MAXN],inv[MAXN];

inline long long power(long long a,long long n)

{

        long long ans = ,b = a;

        while (n > )

        {

                if (n & ) ans = (ans * b) % P;

                b = (b * b) % P;

                n >>= ;

        }

        return ans;

}

inline void init()

{

        int i;

        fac[] = ;

        for (i = ; i < MAXN; i++) fac[i] = fac[i-] * i % P;

        inv[MAXN-] = power(fac[MAXN-],P-);

        for (i = MAXN - ; i >= ; i--) inv[i] = inv[i+] * (i + ) % P;

}

inline long long C(long long n,long long m)

{

        if (!m) return ;

        else if (n == m) return ;

        else return fac[n] * inv[n-m] % P * inv[m] % P;

}

int main() {

        init();

        while (scanf("%d%d",&n,&m) != EOF)

        {

                printf("%lld\n",C(n+m-,n-));

        }

        return ;

}

/*

  f( n! ) = f( (n-1)! n) = f( (n - 1)! ) f(n)

  f( n! ) * f( f(n) ) = f( (n - 1)! )

    f( n! ) * n = f( (n - 1)! )

    f( n! ) = f ( (n + 1)! ) * (n + 1)

*/

巴特西

【HDU 5698】瞬间移动

最新文章

热门文章

巴特西

【HDU 5698】 瞬间移动

最新文章

热门文章

【HDU 5698】瞬间移动