QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#72279#4812. Counting SequenceJinTianHaoAC ✓2543ms949280kbC++171.4kb2023-01-15 11:55:362023-01-15 11:55:40

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 11:55:40]
  • 评测
  • 测评结果:AC
  • 用时:2543ms
  • 内存:949280kb
  • [2023-01-15 11:55:36]
  • 提交

answer

#include <bits/stdc++.h>
#define inf 1000000007
#define mod 998244353
// #define int long long
// #pragma GCC optimize("Ofast","inline","-ffast-math")
// #pragma GCC target("avx,sse2,sse3,sse4,mmx")
using namespace std;
template <typename T> void read(T &x){
	x=0;char ch=getchar();int fh=1;
	while (ch<'0'||ch>'9'){if (ch=='-')fh=-1;ch=getchar();}
	while (ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
	x*=fh;
}
template <typename T> void write(T x) {
	if (x<0) x=-x,putchar('-');
	if (x>9) write(x/10);
	putchar(x%10+'0');
}
template <typename T> void writeln(T x) {
	write(x);
	puts("");
}
int n,c,siz,ans;
int dp1[300005],z[300005];
int dp2[300005][805];
signed main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(n);read(c);dp1[0]=z[0]=1;ans=n>1;
	while(siz*(siz+1)<=2*n) ++siz;
	for(int i=1;i<=siz;++i)
		for(int j=n-siz;j>=0;--j)
		{
			dp1[j]=0;
			if(siz+i<=j) dp1[j]=dp1[j-siz-i];
			if(siz-i<=j) (dp1[j]+=1ll*dp1[j-siz+i]*c%mod)%=mod;
			if(j<n-siz&&(n-siz-j)%(i+1)==0) (ans+=dp1[j])%=mod;
			(z[j]+=dp1[j])%=mod;
		}
	for(int i=1;i<=siz;++i)
		dp2[i][i]=1;
	for(int i=1;i<=n;++i)
		for(int j=1;j<=siz&&j<i;++j)
		{
			dp2[i][j]=dp2[i-j][j-1];
			if(j<siz-1) (dp2[i][j]+=1ll*dp2[i-j][j+1]*c%mod)%=mod;
		}
	for(int i=1;i<siz;++i) (ans+=dp2[n][i])%=mod;
	for(int i=1;i<=n;++i) (ans+=1ll*dp2[i][siz]*z[n-i]%mod)%=mod;
	writeln(ans);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 5392kb

input:

5 3

output:

8

result:

ok 1 number(s): "8"

Test #2:

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

input:

1 0

output:

1

result:

ok 1 number(s): "1"

Test #3:

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

input:

2022 39

output:

273239559

result:

ok 1 number(s): "273239559"

Test #4:

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

input:

1 998244352

output:

1

result:

ok 1 number(s): "1"

Test #5:

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

input:

1 12345678

output:

1

result:

ok 1 number(s): "1"

Test #6:

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

input:

20 998998

output:

643731701

result:

ok 1 number(s): "643731701"

Test #7:

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

input:

23 123

output:

947753998

result:

ok 1 number(s): "947753998"

Test #8:

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

input:

50 5555

output:

745339864

result:

ok 1 number(s): "745339864"

Test #9:

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

input:

60 6666

output:

690992218

result:

ok 1 number(s): "690992218"

Test #10:

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

input:

100 50

output:

169678588

result:

ok 1 number(s): "169678588"

Test #11:

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

input:

500 88888

output:

216149701

result:

ok 1 number(s): "216149701"

Test #12:

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

input:

1000 213456

output:

270989457

result:

ok 1 number(s): "270989457"

Test #13:

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

input:

2000 119988

output:

756425375

result:

ok 1 number(s): "756425375"

Test #14:

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

input:

3000 998244352

output:

71841227

result:

ok 1 number(s): "71841227"

Test #15:

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

input:

3000 555555555

output:

79880116

result:

ok 1 number(s): "79880116"

Test #16:

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

input:

4321 1234

output:

949603993

result:

ok 1 number(s): "949603993"

Test #17:

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

input:

5000 0

output:

5

result:

ok 1 number(s): "5"

Test #18:

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

input:

5000 88888777

output:

833064960

result:

ok 1 number(s): "833064960"

Test #19:

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

input:

5000 35557777

output:

696388498

result:

ok 1 number(s): "696388498"

Test #20:

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

input:

10000 123456

output:

434296902

result:

ok 1 number(s): "434296902"

Test #21:

score: 0
Accepted
time: 38ms
memory: 69568kb

input:

20000 555555

output:

34806915

result:

ok 1 number(s): "34806915"

Test #22:

score: 0
Accepted
time: 74ms
memory: 103024kb

input:

30000 777888999

output:

58443551

result:

ok 1 number(s): "58443551"

Test #23:

score: 0
Accepted
time: 156ms
memory: 166780kb

input:

50000 2

output:

90102905

result:

ok 1 number(s): "90102905"

Test #24:

score: 0
Accepted
time: 253ms
memory: 227140kb

input:

70000 77998866

output:

202638568

result:

ok 1 number(s): "202638568"

Test #25:

score: 0
Accepted
time: 445ms
memory: 320988kb

input:

100000 998244352

output:

360520717

result:

ok 1 number(s): "360520717"

Test #26:

score: 0
Accepted
time: 445ms
memory: 321760kb

input:

100000 555555555

output:

613886009

result:

ok 1 number(s): "613886009"

Test #27:

score: 0
Accepted
time: 926ms
memory: 477772kb

input:

150000 233333

output:

381065878

result:

ok 1 number(s): "381065878"

Test #28:

score: 0
Accepted
time: 913ms
memory: 477752kb

input:

150000 20050117

output:

269891864

result:

ok 1 number(s): "269891864"

Test #29:

score: 0
Accepted
time: 1340ms
memory: 634784kb

input:

200000 114514

output:

262861613

result:

ok 1 number(s): "262861613"

Test #30:

score: 0
Accepted
time: 1338ms
memory: 634320kb

input:

200000 1919810

output:

77872388

result:

ok 1 number(s): "77872388"

Test #31:

score: 0
Accepted
time: 2542ms
memory: 949164kb

input:

300000 0

output:

12

result:

ok 1 number(s): "12"

Test #32:

score: 0
Accepted
time: 2443ms
memory: 949028kb

input:

300000 1

output:

298803948

result:

ok 1 number(s): "298803948"

Test #33:

score: 0
Accepted
time: 2512ms
memory: 949236kb

input:

300000 2

output:

106751203

result:

ok 1 number(s): "106751203"

Test #34:

score: 0
Accepted
time: 2512ms
memory: 949280kb

input:

300000 1234

output:

427045479

result:

ok 1 number(s): "427045479"

Test #35:

score: 0
Accepted
time: 2521ms
memory: 949048kb

input:

300000 2345

output:

441593553

result:

ok 1 number(s): "441593553"

Test #36:

score: 0
Accepted
time: 2443ms
memory: 949168kb

input:

300000 20041115

output:

580367993

result:

ok 1 number(s): "580367993"

Test #37:

score: 0
Accepted
time: 2508ms
memory: 949256kb

input:

300000 20050117

output:

579859619

result:

ok 1 number(s): "579859619"

Test #38:

score: 0
Accepted
time: 2543ms
memory: 949048kb

input:

300000 22223333

output:

596066085

result:

ok 1 number(s): "596066085"

Test #39:

score: 0
Accepted
time: 2468ms
memory: 949164kb

input:

300000 175846372

output:

660364393

result:

ok 1 number(s): "660364393"

Test #40:

score: 0
Accepted
time: 2427ms
memory: 949052kb

input:

299999 9999999

output:

954865020

result:

ok 1 number(s): "954865020"

Test #41:

score: 0
Accepted
time: 2531ms
memory: 949164kb

input:

299998 55556666

output:

904862432

result:

ok 1 number(s): "904862432"

Test #42:

score: 0
Accepted
time: 1214ms
memory: 606264kb

input:

190733 31756136

output:

880544587

result:

ok 1 number(s): "880544587"

Test #43:

score: 0
Accepted
time: 1345ms
memory: 630524kb

input:

198497 463488298

output:

185220207

result:

ok 1 number(s): "185220207"

Test #44:

score: 0
Accepted
time: 2473ms
memory: 948976kb

input:

299997 0

output:

16

result:

ok 1 number(s): "16"

Test #45:

score: 0
Accepted
time: 987ms
memory: 534964kb

input:

168168 296157813

output:

798716760

result:

ok 1 number(s): "798716760"

Test #46:

score: 0
Accepted
time: 555ms
memory: 366748kb

input:

114514 1919810

output:

783513290

result:

ok 1 number(s): "783513290"