QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#72486#4812. Counting SequencexuqinAC ✓5820ms16628kbC++14992b2023-01-15 19:34:142023-01-15 19:34:15

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-01-15 19:34:15]
  • 评测
  • 测评结果：AC
  • 用时：5820ms
  • 内存：16628kb
查看
  • [2023-01-15 19:34:14]
  • 提交

answer

#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;
const int P=998244353, maxn=300020;

int dp[1700][1700], f[2][maxn<<1];

void add(int &x, int y) {x+=y; if(x>=P) x-=P;}

int main() {
	int n, c; scanf("%d%d", &n, &c);
	int S=1; while(S*(S+1)/2<n) ++S;
//	printf("%d\n", S);
	//a1<S
	for(int i=1; i<=n; ++i) {
		for(int j=1; j<i&&j<2*S; ++j) 
			dp[i%(2*S)][j]=(dp[(i-j+2*S)%(2*S)][j-1]+1LL*dp[(i-j+2*S)%(2*S)][j+1]*c%P)%P;
		if(i<S) dp[i][i]=1; 
	}
	int ans=0;
	for(int i=1; i<2*S; ++i) add(ans, dp[n%(2*S)][i]);
	//a1>=S
	f[0][n]=1; int cur=0;
	for(int j=S; j<=n; ++j) add(ans, f[cur][n-j+n]);
	for(int i=2; i<=S; ++i, cur^=1) {
		for(int j=0; j<=2*n; ++j) {
			f[cur^1][j]=0;
			if(j-(i-1)>=0) add(f[cur^1][j], f[cur][j-(i-1)]);
			if(j+(i-1)<=2*n) add(f[cur^1][j], 1LL*f[cur][j+(i-1)]*c%P);
		}
		for(int j=S; j<=n; ++j)
			if(2*n-1LL*i*j>=0&&2*n-1LL*i*j<=2*n) add(ans, f[cur^1][n-i*j+n]);
	}
	printf("%d", ans);
	return 0;
}
源文件, 语言: C++14

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 5680kb

input:

5 3

output:

8

result:

ok 1 number(s): "8"

Test #2:

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

input:

1 0

output:

1

result:

ok 1 number(s): "1"

Test #3:

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

input:

2022 39

output:

273239559

result:

ok 1 number(s): "273239559"

Test #4:

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

input:

1 998244352

output:

1

result:

ok 1 number(s): "1"

Test #5:

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

input:

1 12345678

output:

1

result:

ok 1 number(s): "1"

Test #6:

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

input:

20 998998

output:

643731701

result:

ok 1 number(s): "643731701"

Test #7:

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

input:

23 123

output:

947753998

result:

ok 1 number(s): "947753998"

Test #8:

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

input:

50 5555

output:

745339864

result:

ok 1 number(s): "745339864"

Test #9:

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

input:

60 6666

output:

690992218

result:

ok 1 number(s): "690992218"

Test #10:

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

input:

100 50

output:

169678588

result:

ok 1 number(s): "169678588"

Test #11:

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

input:

500 88888

output:

216149701

result:

ok 1 number(s): "216149701"

Test #12:

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

input:

1000 213456

output:

270989457

result:

ok 1 number(s): "270989457"

Test #13:

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

input:

2000 119988

output:

756425375

result:

ok 1 number(s): "756425375"

Test #14:

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

input:

3000 998244352

output:

71841227

result:

ok 1 number(s): "71841227"

Test #15:

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

input:

3000 555555555

output:

79880116

result:

ok 1 number(s): "79880116"

Test #16:

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

input:

4321 1234

output:

949603993

result:

ok 1 number(s): "949603993"

Test #17:

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

input:

5000 0

output:

5

result:

ok 1 number(s): "5"

Test #18:

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

input:

5000 88888777

output:

833064960

result:

ok 1 number(s): "833064960"

Test #19:

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

input:

5000 35557777

output:

696388498

result:

ok 1 number(s): "696388498"

Test #20:

score: 0
Accepted
time: 24ms
memory: 7812kb

input:

10000 123456

output:

434296902

result:

ok 1 number(s): "434296902"

Test #21:

score: 0
Accepted
time: 71ms
memory: 7916kb

input:

20000 555555

output:

34806915

result:

ok 1 number(s): "34806915"

Test #22:

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

input:

30000 777888999

output:

58443551

result:

ok 1 number(s): "58443551"

Test #23:

score: 0
Accepted
time: 316ms
memory: 8576kb

input:

50000 2

output:

90102905

result:

ok 1 number(s): "90102905"

Test #24:

score: 0
Accepted
time: 542ms
memory: 8720kb

input:

70000 77998866

output:

202638568

result:

ok 1 number(s): "202638568"

Test #25:

score: 0
Accepted
time: 919ms
memory: 9556kb

input:

100000 998244352

output:

360520717

result:

ok 1 number(s): "360520717"

Test #26:

score: 0
Accepted
time: 908ms
memory: 9704kb

input:

100000 555555555

output:

613886009

result:

ok 1 number(s): "613886009"

Test #27:

score: 0
Accepted
time: 1756ms
memory: 13064kb

input:

150000 233333

output:

381065878

result:

ok 1 number(s): "381065878"

Test #28:

score: 0
Accepted
time: 1732ms
memory: 12332kb

input:

150000 20050117

output:

269891864

result:

ok 1 number(s): "269891864"

Test #29:

score: 0
Accepted
time: 2861ms
memory: 13612kb

input:

200000 114514

output:

262861613

result:

ok 1 number(s): "262861613"

Test #30:

score: 0
Accepted
time: 2775ms
memory: 13776kb

input:

200000 1919810

output:

77872388

result:

ok 1 number(s): "77872388"

Test #31:

score: 0
Accepted
time: 5545ms
memory: 16612kb

input:

300000 0

output:

12

result:

ok 1 number(s): "12"

Test #32:

score: 0
Accepted
time: 5694ms
memory: 16580kb

input:

300000 1

output:

298803948

result:

ok 1 number(s): "298803948"

Test #33:

score: 0
Accepted
time: 5528ms
memory: 16444kb

input:

300000 2

output:

106751203

result:

ok 1 number(s): "106751203"

Test #34:

score: 0
Accepted
time: 5496ms
memory: 16628kb

input:

300000 1234

output:

427045479

result:

ok 1 number(s): "427045479"

Test #35:

score: 0
Accepted
time: 5314ms
memory: 16524kb

input:

300000 2345

output:

441593553

result:

ok 1 number(s): "441593553"

Test #36:

score: 0
Accepted
time: 5536ms
memory: 16588kb

input:

300000 20041115

output:

580367993

result:

ok 1 number(s): "580367993"

Test #37:

score: 0
Accepted
time: 5436ms
memory: 16552kb

input:

300000 20050117

output:

579859619

result:

ok 1 number(s): "579859619"

Test #38:

score: 0
Accepted
time: 5555ms
memory: 16620kb

input:

300000 22223333

output:

596066085

result:

ok 1 number(s): "596066085"

Test #39:

score: 0
Accepted
time: 5539ms
memory: 16628kb

input:

300000 175846372

output:

660364393

result:

ok 1 number(s): "660364393"

Test #40:

score: 0
Accepted
time: 5489ms
memory: 16628kb

input:

299999 9999999

output:

954865020

result:

ok 1 number(s): "954865020"

Test #41:

score: 0
Accepted
time: 5820ms
memory: 16608kb

input:

299998 55556666

output:

904862432

result:

ok 1 number(s): "904862432"

Test #42:

score: 0
Accepted
time: 2548ms
memory: 13644kb

input:

190733 31756136

output:

880544587

result:

ok 1 number(s): "880544587"

Test #43:

score: 0
Accepted
time: 2629ms
memory: 13908kb

input:

198497 463488298

output:

185220207

result:

ok 1 number(s): "185220207"

Test #44:

score: 0
Accepted
time: 5539ms
memory: 16588kb

input:

299997 0

output:

16

result:

ok 1 number(s): "16"

Test #45:

score: 0
Accepted
time: 2056ms
memory: 12800kb

input:

168168 296157813

output:

798716760

result:

ok 1 number(s): "798716760"

Test #46:

score: 0
Accepted
time: 1107ms
memory: 11596kb

input:

114514 1919810

output:

783513290

result:

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

服务器时间: 2024-11-30 11:28:02 | 开源项目