| 比赛 |
寒假集训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;
}