东北育才 DAY2组合数取mod (comb)

组合数取模（comb）

【问题描述】

计算C（m,n）mod 9901的值

【输入格式】

从文件comb.in中输入数据。

输入的第一行包含两个整数，m和n

【输出格式】

输出到文件comb.out中。

输出一行，一个整数

【样例输入】

2 1

【样例输出】

2

【数据规模与约定】

对于 20%的数据，n<=m<=20

对于 40%的数据，n<=m<=2000

对于 100%的数据，n<=m<=20000

这道题描述很清楚，有很多种做法，第一题还是挺水的，而且很多网站上也有

自己比较懒，因为摸的数很小，写了一个半打表半lucas。

#include<iostream>

#include<cstring>

#include<cstdio>

using namespace std;

int C[][];

int main()

{

    int i,j;

    int n,m;

    cin>>n>>m;

    for(i=;i<=;i++)

    {

        C[i][i]=;

        C[i][]=;

        C[i][]=;

    }

    for(i=;i<=;i++)

    {

        for(j=;j<=i;j++)

        {

            C[i][j]=((C[i-][j-])%+(C[i-][j])%)%;

        }

    }

    int ans=;

    ans=(C[n/][m/]*C[n%][m%])%;

    cout<<ans;

}

还有一种是直接lucas..

#include<iostream>

#include<cstring>

#include<cstdio>

using namespace std;

typedef long long LL;

LL n,m,p;

LL quick_mod(LL a, LL b)

{

    LL ans=;

    a%=p;

    while(b)

    {

        if(b&)

        {

            ans=ans*a%p;

            b--;

        }

        b>>=;

        a=a*a%p;

    }

    return ans;

}

LL C(LL n, LL m)

{

    if(m>n)

    return ;

    LL ans=;

    for(int i=; i<=m; i++)

    {

        LL a=(n+i-m)%p;

        LL b=i%p;

        ans=ans*(a*quick_mod(b,p-)%p)%p;

    }

    return ans;

}

LL Lucas(LL n, LL m)

{

    if(m == )

    return ;

    return C(n%p,m%p)*Lucas(n/p,m/p)%p;

}

int main()

{

    scanf("%lld%lld", &n, &m);

    p=;

    printf("%lld\n", Lucas(n,m));

    return ;

}

还有一种是直接打表..这里发一下我旁边dalao写的程序

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<cmath>
#include<algorithm>
#define ll long long
using namespace std;
int C[20039]={0};
int main()
{
C[0]=1;
int m,n,a=1,b,stp,STP,MOD=9901;
scanf("%d%d",&m,&n);
while(a<=m)
{
stp=C[0];
for(b=1;b<=a;b++)
{
STP=C[b];
C[b]=stp+C[b];
C[b]%=MOD;
stp=STP;
}
a++;
}
printf("%d",C[n]);
}