Submission #8800138
Source Code Expand
#include<cstdio> using namespace std; typedef long long LL; const int maxn=200005,TT=1000000007; int n,F[4005][4005],fac[8005],inv[8005],A[maxn],B[maxn],ans; inline int read() { int ret=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();} while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=getchar();} return ret*f; } inline int QP(int a,int b) { int ret=1,w=a; while(b) { if(b&1) ret=(LL)ret*w%TT; w=(LL)w*w%TT;b>>=1; } return ret; } inline int C(int n,int m){return (LL)fac[n]*inv[m]%TT*inv[n-m]%TT;} int main() { n=read();fac[0]=1; for(int i=1;i<=8000;i++){fac[i]=(LL)fac[i-1]*i%TT;inv[i]=QP(fac[i],TT-2);} for(int i=1;i<=n;i++) { A[i]=read();B[i]=read(); F[2000-A[i]][2000-B[i]]++; } for(int i=0;i<=4000;i++) for(int j=0;j<=4000;j++) F[i][j]=((LL)F[i][j]+(j?F[i][j-1]:0)+(i?F[i-1][j]:0))%TT; for(int i=1;i<=n;i++) { ans=(ans+F[2000+A[i]][2000+B[i]])%TT; ans=(ans-C(A[i]+B[i]+A[i]+B[i],A[i]+A[i])+TT)%TT; } ans=(LL)ans*QP(2,TT-2)%TT; printf("%d\n",ans); return 0; }
Submission Info
Submission Time | |
---|---|
Task | E - BBQ Hard |
User | XuZhiyuan |
Language | C++14 (GCC 5.4.1) |
Score | 1400 |
Code Size | 1068 Byte |
Status | AC |
Exec Time | 112 ms |
Memory | 64384 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 1400 / 1400 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | sample-01.txt |
All | sample-01.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, sample-01.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
01-01.txt | AC | 83 ms | 62848 KB |
01-02.txt | AC | 83 ms | 62848 KB |
01-03.txt | AC | 97 ms | 63616 KB |
01-04.txt | AC | 109 ms | 64384 KB |
01-05.txt | AC | 112 ms | 64384 KB |
01-06.txt | AC | 100 ms | 64384 KB |
01-07.txt | AC | 83 ms | 62848 KB |
01-08.txt | AC | 91 ms | 64384 KB |
01-09.txt | AC | 100 ms | 64384 KB |
01-10.txt | AC | 102 ms | 64384 KB |
01-11.txt | AC | 102 ms | 64384 KB |
01-12.txt | AC | 101 ms | 64384 KB |
01-13.txt | AC | 108 ms | 64384 KB |
01-14.txt | AC | 109 ms | 64384 KB |
sample-01.txt | AC | 83 ms | 62848 KB |