递推求组合数

// c[a][b] 表示从a个苹果中选b个的方案数
for (int i = 0; i < N; i ++ )
    for (int j = 0; j <= i; j ++ )
        if (!j) c[i][j] = 1;
        else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;

公式求组合数

const int mod=1e9+7;
//f[i] i的阶乘 ,g[i] i的阶乘的逆元 
ll f[10005],g[10005];
int n;

ll power(ll a,ll b,int p){
    ll ans=1;
    while(b){
        if(b&1) ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;

}

ll getC(int n,int m){
    return f[n]*g[m]%mod*g[n-m]%mod;
}
int main(){
    n=1000;
    f[0]=g[0]=1;
    for(int i=1;i<=n;i++){
        f[i]=f[i-1]*i%mod;
        g[i]=g[i-1]*power(i,mod-2,mod)%mod;
    }
    cout<<getC(10,2)<<endl;
}

lucas定理

ll lucas(ll n,ll m,int p){
    if(m==0)return 1;
    return lucas(n/p,m/p,p)*getC(n%p,m%p,p)%p;
}

隔板法

正整数解的个数 c[n-1][k-1]
非负整数解的个数 c[n+k-1][k-1]

容斥 集合的并

集合的并等于集合的交的交错和 奇正偶负

int n,m;
int prime[20];
int main(){
    cin>>n>>m;
    for(int i=0;i<m;i++){
        cin>>prime[i];
    }

    int ans=0;
    for(int i=1;i< 1<<m;i++){
        int t=1,sign=-1;
        for(int j=0;j<m;j++){
            if(i&1<<j){
                if(t*prime[i]>n){
                    t=0;break;
                }
                t*=prime[j];
                sign*=-1;
            }
        }
        if(t) ans+=n/t*sign;
    }
    cout<<ans<<endl;
    return 0;
}

容斥 集合的交

集合的交等于全集减补集的并