Rainy2k
0%

组合数

Posted on Edited on In

1+3+5+...+(2∗n−1)=n21+3+5+...+(2*n-1) = n^2

2+4+6+...+(2∗n)=n∗(n+1)2+4+6+...+(2*n) = n*(n+1)

1+2+3+...+n=n∗(n+1)21+2+3+...+n = \frac{n*(n+1)}{2}

Cnm=Cn−1m−1+Cn−1mC_{n}^{m}= C_{n-1}^{m-1} + C_{n-1}^m

模板

取模

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int f[maxn],inv[maxn];
int qpow(int a,int b){
    int res=1;
    while(b){
        if(b&1)res=res*a%mod;
        a=a*a%mod;;
        b/=2;
    }
    return res;
}
void init(){
    f[0]=1;
    for(int i=1;i<=maxn-1;i++)f[i]=f[i-1]*i%mod;
    inv[maxn-1]=qpow(f[maxn-1],mod-2);
    for(int i=maxn-2;i>=0;i--)inv[i]=inv[i+1]*(i+1)%mod;
}
int C(int n,int m){
    return f[n]*inv[m]%mod*inv[n-m]%mod;
}

数值较小,且不可以取模

1
2
3
4
5
6
7
8
9
10
11
const int maxn = 1000 + 5;
double c[maxn][maxn];
void init() {
    c[0][0] = 1;
    for (int i = 1; i < maxn;i++) {
        c[i][0] = c[i][i] = 1;
        for (int j = 1;j<i;j++) {
            c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
const int mod = 1e9+7;
const int maxn = 2e6+100;

long long f[maxn],inv[maxn];
long long qpow(long long a,long long b){ 
    long long res=1;
    while(b){
        if(b&1)res=res*a%mod;
        a=a*a%mod;;
        b>>=1;
    }
    return res;
}


void init(){
    f[0]=1;
    for(int i=1;i<=maxn-1;i++)f[i]=f[i-1]*i%mod; // A(i,i)
    inv[maxn-1]=qpow(f[maxn-1],mod-2);
    for(int i=maxn-2;i>=0;i--)inv[i]=inv[i+1]*(i+1)%mod;
}

long long C(int n,int m){
    return f[n]*inv[m]%mod*inv[n-m]%mod;
}

数值较小,且不可以取模

1
2
3
4
5
6
7
8
9
10
11
const int maxn = 1000 + 5;
double c[maxn][maxn];
void init() {
    c[0][0] = 1;
    for (int i = 1; i < maxn;i++) {
        c[i][0] = c[i][i] = 1;
        for (int j = 1;j<i;j++) {
            c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
        }
    }
}