组合数

for(int i=0;i<=2000;i++){for(int j=0;j<=i;j++){if(!j) f[i][j]=1;else f[i][j]=(f[i-1][j-1]+f[i-1][j])%mod;}}

快速幂

int quick_pow(int a, int k, int p)
{int res = 1;while (k){if (k & 1) res = (LL)res * a % p;a = (LL)a * a % p;k >>= 1;}return res;
}

费马小定理(Fermat’s little theorem)是数论中的一个重要定理，在1636年提出。如果p是一个质数，而整数a不是p的倍数，则有a（p-1）≡1（mod p）。

#include<iostream>
using namespace std;
const int mod=1e9+7,N=1e5+10;
typedef long long LL;
long long fac[N],infac[N];
int quick_pow(int a, int k, int p)
{int res = 1;while (k){if (k & 1) res = (LL)res * a % p;a = (LL)a * a % p;k >>= 1;}return res;
}
int main()
{int n;fac[0]=infac[0]=1;for(int i=1;i<=1e5;i++){fac[i]=fac[i-1]*i%mod;infac[i]=(LL)infac[i - 1] * quick_pow(i,mod-2,mod)%mod;}cin>>n;while(n--){int a,b;cin>>a>>b;cout<<(LL)fac[a] * infac[b] % mod * infac[a - b] % mod<<endl;}}

devu鲜花

假设N个盒子，第i个盒子里面由Ai支花，总共要选出M支。
1.假设花有无限多，每种花取Xi支，则有
X1+X2+X3+…+Xn=M；
Xi>=0;
令Yi=Xi+1；
Y1+Y2+…+Yn =M+n;
插板法。

2.X1<=A1,X2<=A2…
容斥原理

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
typedef long long ll;
const int N=25;
ll n,m;
int res;
ll a[N];
int down=1;
int ksm(int a,int b) {//快速幂int res=1;while(b) {if(b&1) res=1ll*res*a%mod;a=1ll*a*a%mod;b>>=1;}return res;
}
int C(ll a,ll b) {if(a<b) return 0;int up=1;for(ll i=a; i>a-b; --i) up=i%mod*up%mod;return 1ll*up*down%mod;
}
int main() {scanf("%lld%lld",&n,&m);for(int i=0; i<n; ++i) scanf("%lld",&a[i]);for(int i=1; i<=n-1; ++i) down=1ll*i*down%mod;down=ksm(down,mod-2);for(int i=0; i<(1<<n); ++i) {ll d=m+n-1,up=n-1;int sign=1;for(int j=0; j<n; ++j) {if((i>>j)&1) {sign*=-1;d-=a[j]+1;}}res=(res+C(d,up)*sign)%mod;}printf("%d\n",(res+mod)%mod);return 0;
}