QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#694980#7200. Cliquedongyc666TL 120ms4048kbC++143.4kb2024-10-31 19:04:272024-10-31 19:04:27

Judging History

This is the latest submission verdict.

  • [2024-10-31 19:04:27]
  • Judged
  • Verdict: TL
  • Time: 120ms
  • Memory: 4048kb
  • [2024-10-31 19:04:27]
  • Submitted

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

result: