首页 > 代码库 > nefu 628 Garden visiting

nefu 628 Garden visiting

题目:给出一个n*m大的花园,求出从左上角到右下角的路径数目(路径单调)。

方法:路径数=C(m+n-2,m-1);别忘了最后对p取余。由于数据最大能达到10^5,使用杨辉三角记录的话会爆内存,所以只能换方法。

           由于C(x,y)=x!/(y!*(x-y)!),这里我们可以将x!分解素因子,并保存记录下来,同样的方法记录后面两个,由于x!必然能够整除(y!*(x-y)!),所以后面两个数有的因子,x!比然有,只需要将他们的因子的指数相加减,就能得到最后结果的素因子分解的情况,然后最后使用快速幂取模,就能得到最后的结果。

注意:如何进行素因子分解?

            首先要打表将所有的素因子求出来,这里有是将n!进行素因子分解,假设想要求出其中有多少个5,这里是有技巧的。

            假设n=200,那么因子5的个数=200/5+40/5+8/5=49,怎么得到的呢?200中5的倍数有40个,这40个数中其中是25的倍数的有8个,所以还能分解出8个5,这8个数中还有一个是125的倍数,还能分解出一个5,就这样一直循环下去,就能求出指数的值。

代码:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int prim[17990];
int t[200001];
void init()            //打表求出所有的素数
{
    int k=0;
    memset(t,0,sizeof(t));
    int i,j;
    for(i=2; i<=200000; i++)
        if(!t[i])
        {
            prim[k++]=i;
            for(j=i+i; j<=200000; j+=i)
                t[j]=1;
        }
}
long long exp_mod(int a,int n,int b)    //快速幂取模
{
    long long t;
    if(n==0) return 1%b;
    if(n==1) return a%b;
    t=exp_mod(a,n/2,b);
    t=t*t%b;
    if((n&1)==1) t=t*a%b;
    return t;
}

int getsum(int n,int k)         //获得素因子的指数值
{
    int sum=0;
    while(n!=0)
    {
        sum+=n/k;
        n/=k;
    }
    return sum;
}

int main()
{
    int p,m,n;
    int t,i,j,k;
    init();
    cin>>t;
    while(t--)
    {
        cin>>m>>n>>p;
        if(n>m) swap(n,m);
        m=m+n-2;
        n--;

        int sum=0;
        long long ans=1;
        for(i=0; i<=17984&&prim[i]<=m; i++)
        {
            sum=getsum(m,prim[i])-getsum(n,prim[i])-getsum(m-n,prim[i]);
            if(sum!=0)
                ans=ans*exp_mod(prim[i],sum,p)%p;
            if(ans==0) break;
        }
        cout<<ans<<endl;
    }
    return 0;
}