比赛 寒假集训5 评测结果 AAAAAAAAAA
题目名称 на меня 最终得分 100
用户昵称 123 运行时间 6.051 s
代码语言 C++ 内存使用 140.27 MiB
提交时间 2026-03-01 11:08:42
显示代码纯文本
        #include<iostream>
        #include<cstdio>
        #include<cmath>
        #include<algorithm>
        #include<cstring>
        #define rg register
        using namespace std;
        const int MAXN1=2e5+50,MAXN2=2100,S=2050;
        typedef long long LL;
        LL N,a[MAXN1],b[MAXN1],mul[MAXN2<<2],invv[MAXN2<<2],f[MAXN2<<1][MAXN2<<1],ans=0,MOD;
        inline LL qpow(LL a,LL b){//快速幂 
        	LL res=1;
        	while(b){
        		if(b&1) res=(res*a)%MOD;
        		b>>=1;
        		a=(a*a)%MOD;
        	}
        	return res;
        }
        inline LL inv(LL x){return qpow(x,MOD-2)%MOD;}//求逆元 
        inline LL C(LL n,LL m){return mul[n]*invv[n-m]%MOD*invv[m]%MOD;}//求组合数 
        int main()
        {
        	freopen("BBQ.in","r",stdin); 
        	freopen("BBQ.out","w",stdout); 
        	memset(f,0,sizeof(f));
        	scanf("%lld%lld",&N,&MOD);
        	for(rg LL i=1;i<=N;i++) scanf("%lld%lld",&a[i],&b[i]),f[S-a[i]][S-b[i]]++;//将所有的起点的dp值都加一 
        	mul[0]=1,invv[0]=inv(mul[0]);//预处理阶乘及阶乘逆元 
        	for(rg LL i=1;i<=8000;i++) mul[i]=mul[i-1]*i%MOD,invv[i]=inv(mul[i]);
        	for(rg LL i=1;i<=S*2;i++)//dp 
        		for(rg LL j=1;j<=S*2;j++)
        			f[i][j]=(f[i][j]+(f[i-1][j]+f[i][j-1])%MOD)%MOD;
        	for(rg LL i=1;i<=N;i++){
        		ans=(ans+f[S+a[i]][S+b[i]])%MOD;//累加答案 
        		ans=(ans-C(2*a[i]+2*b[i],2*a[i])+MOD)%MOD;//减去重复计算的 
        	}
        	ans=(ans*qpow(2,MOD-2))%MOD;//除以二,也就是乘2的逆元 
        	printf("%lld\n",ans);
        	return 0;
        }