QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#41397#605. Alternating permutationJohnAlfnovAC ✓14ms18884kbC++20560b2022-07-30 12:11:062022-07-30 12:11:08

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-07-30 12:11:08]
  • 评测
  • 测评结果：AC
  • 用时：14ms
  • 内存：18884kb
查看
  • [2022-07-30 12:11:06]
  • 提交

answer

#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;
int f[2005][2005];
int main(){
	int n,s,t;
	scanf("%d%d%d",&n,&s,&t);
	f[0][0]=1;
	for(int i=1;i<=n;++i){
		int gs=min(i+1,n-i+2);
		if(i==s||i==t){
			for(int j=0;j<=gs;++j){
				f[i][j+1]=(f[i][j+1]+f[i-1][j])%mod;
				if(j)f[i][j]=(f[i][j]+f[i-1][j])%mod;
			}
		}else{
			for(int j=0;j<=gs;++j){
				f[i][j+1]=(f[i][j+1]+1ll*f[i-1][j]*(j+1-(i>s)-(i>t)))%mod;
				if(j)f[i][j-1]=(f[i][j-1]+1ll*f[i-1][j]*(j-1))%mod;
			}
		}
	}
	printf("%d\n",f[n][1]);
	return 0;
}
Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 10ms
memory: 18872kb

input:

2000 249 662

output:

979748465

result:

ok 1 number(s): "979748465"

Test #2:

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

input:

40 3 36

output:

636639342

result:

ok 1 number(s): "636639342"

Test #3:

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

input:

1080 615 886

output:

725146189

result:

ok 1 number(s): "725146189"

Test #4:

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

input:

2000 1505 232

output:

685039198

result:

ok 1 number(s): "685039198"

Test #5:

score: 0
Accepted
time: 14ms
memory: 17972kb

input:

2000 1727 623

output:

826160131

result:

ok 1 number(s): "826160131"

Test #6:

score: 0
Accepted
time: 7ms
memory: 17956kb

input:

2000 226 391

output:

540336141

result:

ok 1 number(s): "540336141"

Test #7:

score: 0
Accepted
time: 9ms
memory: 17936kb

input:

2000 703 1774

output:

376190159

result:

ok 1 number(s): "376190159"

Test #8:

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

input:

2000 1152 1096

output:

279880243

result:

ok 1 number(s): "279880243"

Test #9:

score: 0
Accepted
time: 11ms
memory: 18800kb

input:

1978 1073 500

output:

507169561

result:

ok 1 number(s): "507169561"

Test #10:

score: 0
Accepted
time: 8ms
memory: 18828kb

input:

2000 1992 1525

output:

738562126

result:

ok 1 number(s): "738562126"

Test #11:

score: 0
Accepted
time: 0ms
memory: 6128kb

input:

332 180 96

output:

981869781

result:

ok 1 number(s): "981869781"

Test #12:

score: 0
Accepted
time: 8ms
memory: 18692kb

input:

2000 509 1085

output:

264447286

result:

ok 1 number(s): "264447286"

Test #13:

score: 0
Accepted
time: 9ms
memory: 17964kb

input:

2000 1278 212

output:

205650795

result:

ok 1 number(s): "205650795"

Test #14:

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

input:

2000 1990 211

output:

968979327

result:

ok 1 number(s): "968979327"

Test #15:

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

input:

2000 1149 1516

output:

33004582

result:

ok 1 number(s): "33004582"

Test #16:

score: 0
Accepted
time: 8ms
memory: 18188kb

input:

1864 410 744

output:

472245768

result:

ok 1 number(s): "472245768"

Test #17:

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

input:

13 1 11

output:

101042

result:

ok 1 number(s): "101042"

Test #18:

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

input:

1998 821 973

output:

290007279

result:

ok 1 number(s): "290007279"

Test #19:

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

input:

2000 23 576

output:

932650726

result:

ok 1 number(s): "932650726"

Test #20:

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

input:

1078 504 314

output:

816976522

result:

ok 1 number(s): "816976522"

Test #21:

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

input:

1874 77 1372

output:

236095030

result:

ok 1 number(s): "236095030"

Test #22:

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

input:

2000 1640 910

output:

186485724

result:

ok 1 number(s): "186485724"

Test #23:

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

input:

883 468 652

output:

90531697

result:

ok 1 number(s): "90531697"

Test #24:

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

input:

2000 344 108

output:

473946379

result:

ok 1 number(s): "473946379"

Test #25:

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

input:

1177 728 957

output:

269338492

result:

ok 1 number(s): "269338492"

Test #26:

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

input:

642 351 495

output:

561170740

result:

ok 1 number(s): "561170740"

Test #27:

score: 0
Accepted
time: 9ms
memory: 18812kb

input:

2000 413 817

output:

897052865

result:

ok 1 number(s): "897052865"

Test #28:

score: 0
Accepted
time: 8ms
memory: 17064kb

input:

1767 69 638

output:

135415850

result:

ok 1 number(s): "135415850"

Test #29:

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

input:

2000 184 591

output:

232066123

result:

ok 1 number(s): "232066123"

Test #30:

score: 0
Accepted
time: 10ms
memory: 18028kb

input:

2000 256 348

output:

169245242

result:

ok 1 number(s): "169245242"

Test #31:

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

input:

1383 1029 240

output:

485589486

result:

ok 1 number(s): "485589486"

Test #32:

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

input:

620 15 70

output:

717885415

result:

ok 1 number(s): "717885415"

Test #33:

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

input:

2000 492 26

output:

981676302

result:

ok 1 number(s): "981676302"

Test #34:

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

input:

2000 1233 1252

output:

301114779

result:

ok 1 number(s): "301114779"

Test #35:

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

input:

353 204 113

output:

888055126

result:

ok 1 number(s): "888055126"

Test #36:

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

input:

2000 1030 311

output:

668443332

result:

ok 1 number(s): "668443332"

Test #37:

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

input:

2000 1038 1399

output:

961335740

result:

ok 1 number(s): "961335740"

Test #38:

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

input:

2000 1823 768

output:

927489489

result:

ok 1 number(s): "927489489"

Test #39:

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

input:

2000 753 858

output:

840245065

result:

ok 1 number(s): "840245065"

Test #40:

score: 0
Accepted
time: 10ms
memory: 17940kb

input:

2000 1996 113

output:

320982302

result:

ok 1 number(s): "320982302"

Test #41:

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

input:

1371 95 520

output:

261577724

result:

ok 1 number(s): "261577724"

Test #42:

score: 0
Accepted
time: 6ms
memory: 14600kb

input:

1317 885 324

output:

923532564

result:

ok 1 number(s): "923532564"

Test #43:

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

input:

2000 1156 1043

output:

47705941

result:

ok 1 number(s): "47705941"

Test #44:

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

input:

238 111 146

output:

611855732

result:

ok 1 number(s): "611855732"

Test #45:

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

input:

1486 281 79

output:

473052686

result:

ok 1 number(s): "473052686"

Test #46:

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

input:

2000 1711 1007

output:

931862496

result:

ok 1 number(s): "931862496"

Test #47:

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

input:

1871 1044 803

output:

479361145

result:

ok 1 number(s): "479361145"

Test #48:

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

input:

2000 1196 825

output:

550086503

result:

ok 1 number(s): "550086503"

Test #49:

score: 0
Accepted
time: 6ms
memory: 16348kb

input:

1526 968 659

output:

360125642

result:

ok 1 number(s): "360125642"

Test #50:

score: 0
Accepted
time: 9ms
memory: 18828kb

input:

2000 1640 616

output:

803535642

result:

ok 1 number(s): "803535642"
English 繁體中文 简体中文

Server Time: 2025-02-03 01:03:47 | OpenSource Project