QOJ.ac
QOJ
QOJ is currently under a maintenance. It might be unavailable in the following a few hours.
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#694980 | #7200. Clique | dongyc666 | TL | 120ms | 4048kb | C++14 | 3.4kb | 2024-10-31 19:04:27 | 2024-10-31 19:04: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;
// cout<<sum1<<" "<<sum2<<endl;
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;
// cout<<sum1<<" "<<sum2<<endl;
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;
// cout<<sum1<<" "<<sum2<<endl;
// for(int i=0;i<=M*2;i++)
// if(r1[i])printf("x:%lld %lld\n",i-M,r1[i]);
// for(int i=0;i<=M*2;i++)
// if(c1[i])printf("y:%lld %lld\n",i-M,c1[i]);
// puts("----");
// for(int i=0;i<=M*2;i++)
// if(r3[i])printf("x:%lld %lld %lld\n",i-M,r3[i],C(m,(m+x[3]-i)/2));
// for(int i=0;i<=M*2;i++)
// if(c3[i])printf("y:%lld %lld\n",i-M,c3[i]);
res3=sum1*sum2%MOD;
// cout<<res1<<" "<<res2<<" "<<res3<<endl;
int ans=res1*res2%MOD*res3%MOD;
for(int i=0;i<=M*2;i++)
for(int j=0;j<=M*2;j++)if((i+j)%2==0){
int v1=r1[i]*c1[j]%MOD;
int v2=r2[i]*c2[j]%MOD;
int v3=r3[i]*c3[j]%MOD;
if((i&1)!=((x[1]&1)^(m&1))||(j&1)!=((y[1]&1)^(m&1)))v1=0;
if((i&1)!=((x[a+1]&1)^(m&1))||(j&1)!=((y[a+1]&1)^(m&1)))v2=0;
if((i&1)!=((x[a+b+1]&1)^(m&1))||(j&1)!=((y[a+b+1]&1)^(m&1)))v3=0;
if(!v1&&!v2&&!v3)continue;
// printf("x:%lld y:%lld %lld %lld %lld\n",i-M,j-M,v1,v2,v3);
add(ans,-v1*v2%MOD*res3);
add(ans,-v1*v3%MOD*res2);
add(ans,-v2*v3%MOD*res1);
add(ans,v1*v2%MOD*v3);
}
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: 120ms
memory: 4048kb
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
Time Limit Exceeded
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 796113978 404525295 30866799 194299669 858666576 470561717 648540778 759837943 424564385 854420091 751700956 78610103 110647327 357314368 177769499 849304681 82629517 662149269 863085960 362842390 660600635 796230435 115410011 60517720