萌新刚学容斥半天,求条,宣关
查看原帖
萌新刚学容斥半天,求条,宣关
663199
Tachibana27楼主2024/5/5 13:56
#include<iostream>
#define int long long
#define mod 1000000007
int n,m;
int a[1006];
int fac[1086];
void exgcd(int a,int b,int &x,int &y){
	if(not b){
		x=1;
		y=0;
		return;
	}
	exgcd(b,a%b,x,y);
	int tmp=x;
	x=y;
	y=tmp-y*(a/b);
	return;
}
int f(int n){
    int sum=1;
    for(int i=1;i<=m;i++){
        int xx=0;
        int yy=0;
        exgcd(fac[n-1]*fac[a[i]]%mod,mod,xx,yy);
        xx=(xx%mod+mod)%mod;
        sum=sum*(fac[a[i]+n-1]*xx)%mod;
    }
    return sum%mod;
}
int ans;
signed main(){
    std::cin>>n>>m;
    for(int i=1;i<=m;i++)
        std::cin>>a[i];
    fac[1]=1;
    for(int i=2;i<=1085;i++)
        fac[i]=fac[i-1]*i%mod;
    for(int i=1;i<=n;i++){
        int op=-1;
        if(i&1)
            op=1;
        ans=(ans+op*f(n-i))%mod;
    }
    std::cout<<(ans%mod+mod)%mod<<"\n";
    return 0;
} 

rt,1天了,样例未过

2024/5/5 13:56
加载中...