【FZU 2015 && FZU 2020 】组合+大数取模

题目链接： http://acm.fzu.edu.cn/problem.php?pid=2015

题目链接：http://acm.fzu.edu.cn/problem.php?pid=2020

解题思路：

2015可以利用公式C（n）（r）=C（n-1）（r）+C（n-1）（r-1）打表。

剩下的问题就转换成了如何列出

2020 两个大数相除再取模（比如（a/b）%mod）可以转换成 a*Inv（b，mod），相除取模可以转换成分子乘分母对模数的逆元。

如果题目要你求多个组合数的话，那么也可以打表求出前maxn项 f[i]%mod =（1*2*3*……*i）%mod；

两个输出的时候都要注意判断答案是不是负数，是的话ans+mod。

2015代码

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <cstring>
 5 using namespace std;
 6 
 7 #define mod 1000000007
 8 int f[201][101];
 9 
10 void init()
11 {
12     for(int i=0; i<=200; i++)
13       f[i][0]=f[0][i]=1;
14     for(int i=1; i<=200; i++)
15         for(int j=1; j<=100; j++)
16         {
17             if(i==j)  f[i][j]=1;
18             else
19                f[i][j]=(f[i-1][j]+f[i-1][j-1])%mod;
20         }
21 }
22 
23 int main()
24 {
25     int  n, m;
26     init();
27     while(~scanf("%d%d",&n,&m))
28     {
29         int k=n-n/2-1;
30         __int64 ans=f[n+k-1][n-1];
31         if(m!=-1)
32         {
33             printf("%I64d\n",ans);
34         }
35         else
36         {
37             __int64 tp=f[2*n-1][n-1];
38             ans=(tp-n*ans%mod)%mod;
39             if(ans<0)  ans+=mod;
40             printf("%I64d\n",ans);
41         }
42     }
43     return 0;
44 }

2020题代码：

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<cmath>
 6 using namespace std;
 7 typedef unsigned long long u64;
 8 __int64 Ext_gcd(__int64 a,__int64 b,__int64 &x,__int64 &y){
 9    if(b==0) { x=1, y=0; return a; }
10    __int64 ret= Ext_gcd(b,a%b,y,x);
11    y-= a/b*x;
12    return ret;
13 }
14 __int64 Inv(__int64 a,int m){  ///求除数a对m的逆元；
15    __int64 d,x,y,t= (__int64)m;
16    d= Ext_gcd(a,t,x,y);
17    if(d==1) return (x%t+t)%t;
18    return -1;
19 }
20 int main()
21 {
22    int T,i,n,m,mod;
23    cin>>T;
24    while(T--){
25        scanf("%d%d%d",&n,&m,&mod);
26        __int64 sum=1;
27        for(i=n-m+1;i<=n;i++){
28            sum*= (__int64)i;
29            sum%= mod;
30        }
31 
32        __int64 tmp=1;
33        for(i=2;i<=m;i++) tmp*= i, tmp%= mod; 
34 
35        sum*= Inv(tmp,mod);
36        sum%= mod;
37        printf("%I64d\n",sum);
38    }
39 }

【FZU 2015 && FZU 2020 】 组合+大数取模

【FZU 2015 && FZU 2020 】组合+大数取模