QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#21275#2816. 过河卒二WhybullYMe#AC ✓169ms4348kbC++143.0kb2022-03-04 14:24:252022-05-08 02:49:13

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-05-08 02:49:13]
  • 评测
  • 测评结果:AC
  • 用时:169ms
  • 内存:4348kb
  • [2022-03-04 14:24:25]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define ri int
typedef long long ll;
const int maxn=33,mod=59393;
template<class T>inline bool ckmin(T &x,const T &y){return x>y?x=y,1:0;}
template<class T>inline bool ckmax(T &x,const T &y){return x<y?x=y,1:0;}
template<class T>inline void clear(T *arr,int siz,int val=0){memset(arr,val,sizeof(T)*(siz+1));}
struct modint{
	int val;
	inline modint(int val_=0):val(val_){}
	inline modint &operator=(int val_){return val=val_,*this;}
	inline modint &operator+=(const modint &k){return val=val+k.val>=mod?val+k.val-mod:val+k.val,*this;}
	inline modint &operator-=(const modint &k){return val=val-k.val<0?val-k.val+mod:val-k.val,*this;}
	inline modint &operator*=(const modint &k){return val=1ll*val*k.val%mod,*this;}
	inline modint &operator^=(int k){
	    modint ret=1,tmp=*this;
	    for(;k;k>>=1,tmp*=tmp)if(k&1)ret*=tmp;
	    return val=ret.val,*this;
	}
	inline modint &operator/=(modint k){return *this*=(k^=mod-2);}
	inline modint &operator+=(int k){return val=val+k>=mod?val+k-mod:val+k,*this;}
	inline modint &operator-=(int k){return val=val<k?val-k+mod:val-k,*this;}
	inline modint &operator*=(int k){return val=1ll*val*k%mod,*this;}
	inline modint &operator/=(int k){return *this*=((modint(k))^=mod-2);}
	template<class T>friend modint operator+(modint a,T b){return a+=b;}
	template<class T>friend modint operator-(modint a,T b){return a-=b;}
	template<class T>friend modint operator*(modint a,T b){return a*=b;}
	template<class T>friend modint operator^(modint a,T b){return a/=b;}
	template<class T>friend modint operator/(modint a,T b){return a/=b;}
	friend modint operator^(modint a,int b){return a^=b;}
	friend bool operator==(modint a,int b){return a.val==b;}
	friend bool operator!=(modint a,int b){return a.val!=b;}
	inline bool operator!(){return !val;}
	inline modint operator-(){return val?mod-val:0;}
	inline modint &operator++(){return *this+=1;}
};
using mi=modint;
mi fac[mod],ifac[mod];
inline void init(){
	fac[0]=1;
	for(ri i=1;i<mod;++i)fac[i]=fac[i-1]*i;
	ifac[mod-1]=1/fac[mod-1];
	for(ri i=mod-1;i;--i)ifac[i-1]=ifac[i]*i;
}
inline mi C(int x,int y){
	if(x<y||y<0)return 0;
	return fac[x]*ifac[y]*ifac[x-y];
}
inline mi lucas(int x,int y){
	if(!y)return 1;
	return C(x%mod,y%mod)*lucas(x/mod,y/mod);
}
inline mi calc(int x,int y){
	if(x<0||y<0)return 0;
	mi ret=0;
	for(ri i=min(x,y);~i;--i)ret+=lucas(x+y-i,i)*lucas(x+y-(i<<1),x-i);
	return ret;
}
mi ans,f[maxn][maxn];
int k,m,n;
int main(){
	init();
	scanf("%d%d%d",&n,&m,&k);
	typedef pair<int,int> pii;
	#define fi first
	#define se second
	vector<pii>p(k+2);
	p[0]={1,1};
	for(ri i=1;i<=k;++i)scanf("%d%d",&p[i].fi,&p[i].se);
	p[++k]={n+1,m+1};
	sort(p.begin(),p.end());
	for(ri i=0;i<k;++i)
		for(ri j=i+1;j<=k;++j)
			f[i][j]=calc(p[j].fi-p[i].fi,p[j].se-p[i].se);
	for(ri i=1<<k-1;i<1<<k;++i){
		ri cur=0;
		mi sum=1;
		for(ri j=1;j<k;++j)
			if(i&(1<<j-1))
				sum*=f[cur][j],cur=j;
		sum*=f[cur][k];
		ans+=(__builtin_parity(i)?1:mod-1)*sum;
	}
	printf("%d",ans);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 73ms
memory: 4176kb

input:

1737 2613 20
1695 2081
1449 1419
868 1636
879 2454
1400 1778
1364 2166
1343 1563
1229 2012
1308 1674
1712 2004
1392 1716
1118 1690
1693 1986
1641 2221
1454 1937
1554 1944
997 2083
1242 1503
990 1834
986 1438

output:

47388

result:

ok single line: '47388'

Test #2:

score: 0
Accepted
time: 105ms
memory: 4140kb

input:

37183 50656 20
19376 46381
26095 33186
22143 36608
22985 46098
37134 47561
29505 37971
33937 39976
30735 35845
18593 27027
24886 31630
31919 48391
31646 31818
32959 30489
28111 33154
19190 30567
21345 33181
27168 29608
25105 37750
27601 30901
31909 28946

output:

24648

result:

ok single line: '24648'

Test #3:

score: 0
Accepted
time: 109ms
memory: 4288kb

input:

44420 91969 20
26580 82240
39885 61285
41566 67220
36272 54211
43473 80094
35306 85527
24022 61262
29798 81055
24511 76963
39082 63249
31639 48137
36127 50250
24651 59458
31061 75543
33310 62799
34926 60731
38397 91900
30238 55599
37632 78084
30203 68381

output:

15204

result:

ok single line: '15204'

Test #4:

score: 0
Accepted
time: 2ms
memory: 4252kb

input:

580805600 54167 0

output:

23746

result:

ok single line: '23746'

Test #5:

score: 0
Accepted
time: 138ms
memory: 4272kb

input:

826964258 69871 20
549552592 47200
515793697 54386
614188758 68095
562588168 39532
442360278 63494
548867812 64969
431340934 47675
754746960 67013
465366759 64806
468411232 57998
642243607 57593
460525676 54551
537102308 66550
497820482 69282
512530411 44066
804850336 62103
647345365 43172
415023030...

output:

13365

result:

ok single line: '13365'

Test #6:

score: 0
Accepted
time: 143ms
memory: 4148kb

input:

730956188 82754 20
446994358 80794
370767296 72114
588336811 61575
461868174 59127
687944030 47654
415192065 64512
676919795 68879
501594582 79353
500183604 77871
369691859 45105
700735165 64997
710627893 76323
422390555 64482
455803600 71287
531930698 60905
512993094 76984
448561503 47257
433564005...

output:

11564

result:

ok single line: '11564'

Test #7:

score: 0
Accepted
time: 4ms
memory: 4276kb

input:

33024 81694 0

output:

34973

result:

ok single line: '34973'

Test #8:

score: 0
Accepted
time: 106ms
memory: 4140kb

input:

32506 85138 20
32235 51865
18196 73834
21810 62856
25280 78735
29905 81850
20980 62326
32392 84165
26666 47713
16292 44472
21821 52166
17956 63418
22186 71351
21874 55903
30929 44205
28833 69843
22645 68970
18044 60713
22875 84981
16932 48656
19083 73733

output:

11558

result:

ok single line: '11558'

Test #9:

score: 0
Accepted
time: 99ms
memory: 4348kb

input:

28794 91901 20
15780 47550
16228 63624
22519 67507
27276 68129
20208 55660
14445 83194
19890 87105
16995 51790
23562 81574
24909 81655
19645 91242
21712 69349
18700 87961
16386 80377
22261 73605
17150 71793
25231 88055
19094 48227
21872 51066
21575 62419

output:

6126

result:

ok single line: '6126'

Test #10:

score: 0
Accepted
time: 5ms
memory: 4288kb

input:

874334884 76845 0

output:

49888

result:

ok single line: '49888'

Test #11:

score: 0
Accepted
time: 5ms
memory: 4208kb

input:

600400150 76601 0

output:

36078

result:

ok single line: '36078'

Test #12:

score: 0
Accepted
time: 78ms
memory: 4272kb

input:

1809 1900 20
1409 1731
1270 1624
1785 1625
1535 1623
1237 1454
1192 1885
1061 1017
1234 1426
1568 1524
1371 1720
924 1436
1150 1642
1577 1203
1381 980
1803 1492
1730 1723
1017 1618
1081 1825
1109 1854
1531 1723

output:

9086

result:

ok single line: '9086'

Test #13:

score: 0
Accepted
time: 37ms
memory: 4204kb

input:

657937727 76253 16
353360364 70916
357516312 53327
589177133 67883
597034765 50623
384898823 58437
379751019 57493
483681045 56498
491539894 53349
610557723 52343
360648343 54993
564102363 39521
419962522 48853
335872303 57105
349100555 67118
468779229 40570
356587597 52710

output:

6809

result:

ok single line: '6809'

Test #14:

score: 0
Accepted
time: 33ms
memory: 4208kb

input:

557724458 54762 14
301629598 47965
436413263 32002
511367835 52269
501044435 50636
299578901 28534
442296296 27498
448704742 41005
363834222 40929
525245696 46031
416274768 51532
415318717 51977
471948030 35370
360058356 49586
440592956 42732

output:

48600

result:

ok single line: '48600'

Test #15:

score: 0
Accepted
time: 150ms
memory: 4152kb

input:

859488244 92109 20
544104338 69060
574192703 77696
486974372 51244
838791582 58699
789748054 55477
604464016 48730
563348127 71652
604126025 60353
670354360 83868
545369547 61775
500525928 49175
432206293 59438
610533110 86479
725144760 71616
693875041 80105
569929288 63697
598742162 71768
677965652...

output:

38594

result:

ok single line: '38594'

Test #16:

score: 0
Accepted
time: 126ms
memory: 4204kb

input:

571070677 52797 20
400551828 30665
417408550 42374
556056493 29785
545655329 28420
484510833 34597
394794339 26740
393526624 40979
436842959 38386
334890610 26606
454767316 37800
537509244 26471
414205915 49455
307519590 30092
544680508 49131
570832559 47979
314571056 49645
361844188 27979
425374340...

output:

49481

result:

ok single line: '49481'

Test #17:

score: 0
Accepted
time: 128ms
memory: 4244kb

input:

567821896 50758 20
321797528 49814
374121935 45703
490334188 45215
314721780 34261
451832051 32195
526382301 35211
408792934 30303
480618183 25425
322239004 41763
293013851 27555
546634104 47215
328456647 44971
319292507 32076
321272107 33387
547421667 45073
545966920 39232
412035955 37941
520427824...

output:

16479

result:

ok single line: '16479'

Test #18:

score: 0
Accepted
time: 127ms
memory: 4288kb

input:

829753401 69714 20
828274315 53293
441063740 68010
698899637 58231
416172227 50421
816338110 51423
567894784 60791
523156675 59065
425721069 48231
472508977 41852
553049724 65905
427790091 61017
433173036 57318
451714261 55511
447745667 41203
677368642 50502
461038435 43078
421673283 64698
535187871...

output:

4298

result:

ok single line: '4298'

Test #19:

score: 0
Accepted
time: 3ms
memory: 4292kb

input:

3 3 3
2 2
2 3
3 2

output:

4

result:

ok single line: '4'

Test #20:

score: 0
Accepted
time: 1ms
memory: 4180kb

input:

873835081 1 1
233 1

output:

464

result:

ok single line: '464'

Test #21:

score: 0
Accepted
time: 104ms
memory: 4204kb

input:

701639588 65456 20
20 1
19 2
18 3
17 4
16 5
15 6
14 7
13 8
12 9
11 10
10 11
9 12
8 13
7 14
6 15
5 16
4 17
3 18
2 19
1 20

output:

3978

result:

ok single line: '3978'

Test #22:

score: 0
Accepted
time: 4ms
memory: 4276kb

input:

849211396 72758 3
1 2
2 1
2 2

output:

0

result:

ok single line: '0'

Test #23:

score: 0
Accepted
time: 4ms
memory: 4200kb

input:

28361 5 0

output:

26840

result:

ok single line: '26840'

Test #24:

score: 0
Accepted
time: 76ms
memory: 4288kb

input:

739003251 85837 19
9 1
8 2
7 3
6 4
5 5
4 6
3 7
2 8
1 9
10 1
9 2
8 3
7 4
6 5
5 6
4 7
3 8
2 9
1 10

output:

0

result:

ok single line: '0'

Test #25:

score: 0
Accepted
time: 169ms
memory: 4292kb

input:

507994226 96662 20
284011294 62806
284011294 62807
284011294 62808
284011295 62806
284011295 62808
284011296 62806
284011296 62807
284011296 62808
488809005 61432
407416480 52884
453544878 55418
479921899 93244
391347376 69358
286757302 80030
398726073 58037
462496452 83242
462496451 83242
462496453...

output:

44165

result:

ok single line: '44165'

Test #26:

score: 0
Accepted
time: 140ms
memory: 4288kb

input:

811734066 68881 20
555484862 68881
584626108 59286
811734066 68881
485588255 46189
493509169 38906
521875803 60358
530848207 41681
755512545 68881
811734066 51709
451042683 47790
681190796 48083
593014418 55702
763130281 43438
684714882 49051
791604023 54672
738158852 63435
811734066 55936
757540221...

output:

17066

result:

ok single line: '17066'

Test #27:

score: 0
Accepted
time: 116ms
memory: 4180kb

input:

719906313 53423 20
606574998 35079
606574999 35079
606574997 35079
598361139 53384
570753681 49836
573910670 38732
427670480 45517
410946812 47351
649756131 46500
649756133 46500
649756132 46501
649756132 46499
432262915 27119
406363477 48245
630227996 30441
526431392 52368
409342397 39014
560125856...

output:

16397

result:

ok single line: '16397'

Test #28:

score: 0
Accepted
time: 157ms
memory: 4272kb

input:

704271417 92848 20
534221616 57197
534030676 49952
529264547 60547
366697878 60100
355234832 55539
608719578 91610
700793935 56558
584423467 81540
432441768 62743
540852563 65916
534221617 57197
534030677 49952
529264548 60547
366697879 60100
355234833 55539
608719579 91610
700793936 56558
584423468...

output:

4464

result:

ok single line: '4464'

Test #29:

score: 0
Accepted
time: 76ms
memory: 4152kb

input:

571503360 92367 19
571503351 92367
571503352 92367
571503353 92367
571503354 92367
571503355 92367
571503356 92367
571503357 92367
571503358 92367
571503359 92367
571503360 92367
571503360 92366
571503360 92365
571503360 92364
571503360 92363
571503360 92362
571503360 92361
571503360 92360
571503360...

output:

15311

result:

ok single line: '15311'

Test #30:

score: 0
Accepted
time: 77ms
memory: 4344kb

input:

48913 9 20
47423 9
40190 4
42976 7
31269 6
25293 8
40386 7
44085 5
34147 7
36001 9
33675 5
37520 7
28913 9
41113 7
29853 9
34528 6
30834 8
46176 7
34012 5
37849 8
34960 6

output:

57975

result:

ok single line: '57975'

Test #31:

score: 0
Accepted
time: 73ms
memory: 4204kb

input:

45953 9 20
44300 8
31177 7
30055 6
26867 8
31774 9
43485 6
41933 9
43902 4
30082 7
37977 7
31152 6
31876 9
27661 6
38824 8
38769 9
33768 7
39013 7
35137 6
28438 9
40478 8

output:

58444

result:

ok single line: '58444'

Test #32:

score: 0
Accepted
time: 1ms
memory: 4180kb

input:

884877140 5 0

output:

50291

result:

ok single line: '50291'

Test #33:

score: 0
Accepted
time: 77ms
memory: 4208kb

input:

773735608 10 20
434780922 8
459862387 10
598361139 6
570753681 10
737688182 5
427670480 8
410946812 6
649756131 8
520725240 10
432262915 8
526431392 8
549026451 10
409342397 6
421060472 8
704271417 7
640920306 5
534221616 9
534030676 10
529264547 5
395217379 8

output:

17180

result:

ok single line: '17180'

Test #34:

score: 0
Accepted
time: 73ms
memory: 4272kb

input:

608719578 5 20
540038792 5
584423467 4
432441768 5
540852563 2
501183788 5
547016517 3
388941970 4
358579302 4
351620759 2
336499263 5
519341861 4
537713518 5
477509895 3
404357527 4
383929357 5
344543931 4
362230509 3
454582199 3
571503360 5
325607169 3

output:

42628

result:

ok single line: '42628'

Test #35:

score: 0
Accepted
time: 4ms
memory: 4256kb

input:

47785 96479 0

output:

2711

result:

ok single line: '2711'