QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#695021#7200. Cliquedongyc666WA 109ms4000kbC++143.0kb2024-10-31 19:09:272024-10-31 19:09:27

Judging History

This is the latest submission verdict.

  • [2024-10-31 19:09:27]
  • Judged
  • Verdict: WA
  • Time: 109ms
  • Memory: 4000kb
  • [2024-10-31 19:09: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;
	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'