QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#695021 | #7200. Clique | dongyc666 | WA | 109ms | 4000kb | C++14 | 3.0kb | 2024-10-31 19:09:27 | 2024-10-31 19:09:27 |
Judging History
answer
#pragma GCC optimize("Ofast,unroll-loops,-finline")
#include<bits/stdc++.h>
using namespace std;
const int NR=4e3+10;
const int MR=6e3+10;
const int M=3002;
#define int long long
const int MOD=1e9+7;
int n,m,a,b,x[NR],y[NR],fac[NR],ifac[NR];
int r1[MR],c1[MR],r2[MR],c2[MR],r3[MR],c3[MR];
void add(int &x,int y){x=(x+y)%MOD;}
void times(int &x,int y){x=x*y%MOD;}
int qpow(int x,int y){
int res=1;
while(y){
if(y&1)res=res*x%MOD;
x=x*x%MOD;y>>=1;
}
return res;
}
int Inv(int x){return qpow(x,MOD-2);}
int C(int x,int y){
if(y<0||y>x)return 0;
return fac[x]*ifac[y]%MOD*ifac[x-y]%MOD;
}
void solve(){
for(int i=1,v1,v2;i<=n;i++){
cin>>v1>>v2;
x[i]=v1+v2+M;y[i]=v1-v2+M;
}
for(int i=0;i<=M*2;i++){
r1[i]=r2[i]=r3[i]=1;
for(int j=1;j<=a;j++)times(r1[i],C(m,(m+x[j]-i)/2));
for(int j=a+1;j<=a+b;j++)times(r2[i],C(m,(m+x[j]-i)/2));
for(int j=a+b+1;j<=n;j++)times(r3[i],C(m,(m+x[j]-i)/2));
}
for(int i=0;i<=M*2;i++){
c1[i]=c2[i]=c3[i]=1;
for(int j=1;j<=a;j++)times(c1[i],C(m,(m+y[j]-i)/2));
for(int j=a+1;j<=a+b;j++)times(c2[i],C(m,(m+y[j]-i)/2));
for(int j=a+b+1;j<=n;j++)times(c3[i],C(m,(m+y[j]-i)/2));
}
int res1=1,res2=1,res3=1;
for(int i=2;i<=a;i++)
if((x[i]&1)!=(x[1]&1)||(y[i]&1)!=(y[1]&1)){
puts("0");
return;
}
for(int i=a+2;i<=a+b;i++)
if((x[i]&1)!=(x[a+1]&1)||(y[i]&1)!=(y[a+1]&1)){
puts("0");
return;
}
for(int i=a+b+1;i<=n;i++)
if((x[i]&1)!=(x[a+b+1]&1)||(y[i]&1)!=(y[a+b+1]&1)){
puts("0");
return;
}
int sum1=0,sum2=0;
for(int i=0;i<=M*2;i++)
if((i&1)==((x[1]&1)^(m&1)))add(sum1,c1[i]);
else c1[i]=0;
for(int i=0;i<=M*2;i++)
if((i&1)==((y[1]&1)^(m&1)))add(sum2,r1[i]);
else r1[i]=0;
res1=sum1*sum2%MOD;
sum1=0,sum2=0;
for(int i=0;i<=M*2;i++)
if((i&1)==((x[a+1]&1)^(m&1)))add(sum1,c2[i]);
else c2[i]=0;
for(int i=0;i<=M*2;i++)
if((i&1)==((y[a+1]&1)^(m&1)))add(sum2,r2[i]);
else r2[i]=0;
res2=sum1*sum2%MOD;
sum1=0,sum2=0;
for(int i=0;i<=M*2;i++)
if((i&1)==((x[a+b+1]&1)^(m&1)))add(sum1,c3[i]);
else c3[i]=0;
for(int i=0;i<=M*2;i++)
if((i&1)==((y[a+b+1]&1)^(m&1)))add(sum2,r3[i]);
else r3[i]=0;
res3=sum1*sum2%MOD;
int ans=res1*res2%MOD*res3%MOD;
sum1=0,sum2=0;
for(int i=0;i<=M*2;i++)add(sum1,r1[i]*r2[i]);
for(int i=0;i<=M*2;i++)add(sum2,c1[i]*c2[i]);
add(ans,-sum1*sum2%MOD*res3);
sum1=0,sum2=0;
for(int i=0;i<=M*2;i++)add(sum1,r1[i]*r3[i]);
for(int i=0;i<=M*2;i++)add(sum2,c1[i]*c3[i]);
add(ans,-sum1*sum2%MOD*res2);
sum1=0,sum2=0;
for(int i=0;i<=M*2;i++)add(sum1,r3[i]*r2[i]);
for(int i=0;i<=M*2;i++)add(sum2,c3[i]*c2[i]);
add(ans,-sum1*sum2%MOD*res1);
sum1=0,sum2=0;
for(int i=0;i<=M*2;i++)add(sum1,r1[i]*r2[i]%MOD*r3[i]);
for(int i=0;i<=M*2;i++)add(sum2,c1[i]*c2[i]%MOD*c3[i]);
add(ans,-sum1*sum2);
cout<<(ans+MOD)%MOD<<endl;
}
signed main(){
fac[0]=ifac[0]=1;
for(int i=1;i<NR;i++)
fac[i]=fac[i-1]*i%MOD,ifac[i]=ifac[i-1]*Inv(i)%MOD;
while(cin>>n>>a>>b>>m)solve();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 2ms
memory: 3996kb
input:
3 1 1 1 0 0 0 1 0 2 3 1 1 4 0 0 0 1 0 2
output:
60 15974400
result:
ok 2 tokens
Test #2:
score: -100
Wrong Answer
time: 109ms
memory: 4000kb
input:
3 1 1 816 -97 60 -78 71 -81 -59 3 1 1 787 -74 -54 -69 -76 69 -76 3 1 1 491 -93 -41 -27 40 34 -73 3 1 1 576 -30 -88 -95 -48 -84 86 3 1 1 158 91 1 -9 86 -19 -76 3 1 1 326 -61 -5 -17 96 -44 74 3 1 1 283 14 -12 -94 -18 7 -37 3 1 1 126 37 -41 -89 76 1 -21 3 1 1 893 -77 -71 -39 67 -82 20 3 1 1 576 14 77 8...
output:
58228093 415913237 565203629 117000370 526652322 941603108 505772314 404525295 585644302 4255400 858666576 767520329 648540778 759837943 833351958 854420091 279501922 248115600 375112998 749883220 177769499 849304681 813108664 662149269 863085960 362842390 660600635 796230435 280695491 60517720 1600...
result:
wrong answer 7th words differ - expected: '941284810', found: '505772314'