求组合数、求逆元、求阶乘 O(n)

在O(n)的时间内求组合数、求逆元、求阶乘。·。·

 1 #include <iostream>
 2 #include <cstdio>
 3 #define ll long long
 4 const int N=200005;//1e5越界
 5 const ll M=1e9+7;
 6 using namespace std;
 7 ll fac[N]={1,1},inv[N]={1,1},fi[N]={1,1};//fac[i]是i的阶乘，inv[i]是i的逆元,fi[i]是i之前的很多逆元求得阶乘，（将除i取模变为乘i的逆元取模
 8  
 9 void init()
10 {
11     for(int i=2;i<N;i++)
12     {
13         fac[i]=fac[i-1]*i%M;
14         inv[i]=(M-M/i)*inv[M%i]%M;
15         fi[i]=inv[i]*fi[i-1]%M;
16     }//递推保存fac阶乘，和fi各个逆元取模相乘
17 }
18 ll C(ll a,ll b)
19 {
20     return fac[a]*fi[b]%M*fi[a-b]%M;//C(a,b)=a!/(b!*(a-b)!)
21 }
22 int main()
23 {
24     init();
25     int n,m;
26     while(~scanf("%d%d",&n,&m))
27     {
28         cout<<C(m+n-4,m-2)<<endl;//求组合数
29     }
30     return 0;
31 }

拓展欧几里得求逆元：

 1 #include<bits/stdc++.h>
 2 #define pi acos(-1)
 3 using namespace std;
 4 typedef long long LL;
 5 typedef pair<int, int> P;
 6 const LL INF = 0x3f3f3f3f;
 7 const int maxn = 3e6 + 10;
 8 const LL mod = 1e9 + 7;
 9 
10 
11 void exgcd(LL a, LL b, LL &x, LL &y)    //拓展欧几里得算法
12 {
13     if(!b) x = 1, y = 0;
14     else
15     {
16         exgcd(b, a % b, y, x);
17         y -= x * (a / b);
18     }
19 }
20 
21 LL niYuan(LL a, LL b)   //求a对b取模的逆元
22 {
23     LL x, y;
24     exgcd(a, b, x, y);
25     return (x + b) % b;
26 }
27 
28 
29 int main()
30 {
31     LL n, p;
32     cin >> n >> p;
33     for(int i=1; i<=n; i++){
34         printf("%lld
", niYuan(i,p));
35     }
36 
37 
38 }