容斥原理

//容斥原理

//时间复杂度O(2^n-1)

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e6+10;
int n,m,res,p[N];
signed main()
{
    cin>>n>>m;
    for(int i=0;i<m;i++) cin>>p[i];
    for(int i=1;i<1<<m;i++){//枚举2^n-1次,因为有这些种可能
        int cnt=0,t=1;
        for(int j=0;j<m;j++){
            if(i>>j&1){
                cnt++;
                t*=p[j];
                if(t>n) break; 
            }
        }
        if(cnt%2) res+=n/t; //如果是奇数,就加上
        else res-=n/t;
    }
    cout<<res<<endl;
    return 0;
}

//分特产
//https://www.luogu.com.cn/problem/P5505

//假设此时有i个人得不到第j个特产,则n-i个人分a[j]个特产,根据插板法可以得到
//方案数为 C(a[j]+n-i-1,n-i-1),而此时又要选择i个人,所以有C(n,i)个方法,根据乘法原理
//再使用容斥原理删除一些不合法的状态即可
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5000,mod=1e9+7;
int n,m,fac[N],_fac[N],k,a[N],res;
int qpow(int a,int k)
{
    int res=1;
    while(k){
        if(k&1) res=res*a%mod;
        a=a*a%mod,k/=2;
    }
    return res;
}
int C(int a,int b)
{
    return fac[a]*_fac[b]%mod*_fac[a-b]%mod;
}
signed main()
{
    cin>>n>>m;
    fac[0]=_fac[0]=1,k=1;
    for(int i=1;i<N;i++) fac[i]=fac[i-1]*i%mod;
    _fac[N-1]=qpow(fac[N-1],mod-2);
    for(int i=N-2;i;i--) _fac[i]=(i+1)*_fac[i+1]%mod;
    for(int i=1;i<=m;i++) cin>>a[i];
    for(int i=0;i<n;i++,k=-k){
        int cnt=1;
        for(int j=1;j<=m;j++) cnt=cnt*C(a[j]+n-i-1,n-i-1)%mod;
        res=(res+C(n,i)*k%mod*cnt%mod+mod)%mod;
    }
    cout<<res;
    return 0;
}