QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#72262#4812. Counting SequenceJinTianHaoWA 17ms22684kbC++171.7kb2023-01-15 11:40:282023-01-15 11:40:29

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:40:29]
  • 评测
  • 测评结果:WA
  • 用时:17ms
  • 内存:22684kb
  • [2023-01-15 11:40:28]
  • 提交

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[2][600005];
int dp2[300005][900];
signed main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(n);read(c);ans=(n>1&&!c);
	siz=sqrt(2*n)-10;siz=max(siz,0);
	while((siz+2)*(siz+1)<=2*n) ++siz;
	dp1[1][n]=1;
	for(int i=1;i<siz;++i)
	{
		for(int j=0;j<=2*n;++j)
			dp1[i&1^1][j]=0;
		for(int j=0;j<=2*n;++j)
		{
			//add <
			(dp1[i&1^1][j+i]+=dp1[i&1][j])%=mod;
			//add >
			(dp1[i&1^1][j-i]+=1ll*c*dp1[i&1][j]%mod)%=mod;
		}
		for(int a=siz+1;a<=n;++a)
		{
			int sum=2*n-a*i;
			if(sum>=0&&sum<=2*n) (ans+=dp1[i&1][sum])%=mod;
		}
	}
	for(int i=1;i<=n;++i)
	{
		if(i<=siz) (dp2[i][i]+=1)%=mod;
		for(int j=1;j<900;++j)
		{
			if(!dp2[i][j]) continue;
			if(i+j-1<=n&&j>1) (dp2[i+j-1][j-1]+=1ll*c*dp2[i][j]%mod)%=mod;
			if(i+j+1<=n&&j<899) (dp2[i+j+1][j+1]+=dp2[i][j])%=mod;
		}
	}
	for(int i=1;i<900;++i)
		(ans+=dp2[n][i])%=mod;
	for(int a=siz+1;a<=n;++a)
		for(int m=siz;m<=siz;++m)
		{
			int sum=2*n-a*m;
			if(sum>=0&&sum<=2*n) (ans+=dp1[m&1][sum])%=mod;
		}
	writeln(ans);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

5 3

output:

8

result:

ok 1 number(s): "8"

Test #2:

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

input:

1 0

output:

1

result:

ok 1 number(s): "1"

Test #3:

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

input:

2022 39

output:

273239559

result:

ok 1 number(s): "273239559"

Test #4:

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

input:

1 998244352

output:

1

result:

ok 1 number(s): "1"

Test #5:

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

input:

1 12345678

output:

1

result:

ok 1 number(s): "1"

Test #6:

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

input:

20 998998

output:

643731701

result:

ok 1 number(s): "643731701"

Test #7:

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

input:

23 123

output:

947753998

result:

ok 1 number(s): "947753998"

Test #8:

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

input:

50 5555

output:

745339864

result:

ok 1 number(s): "745339864"

Test #9:

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

input:

60 6666

output:

690992218

result:

ok 1 number(s): "690992218"

Test #10:

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

input:

100 50

output:

169678588

result:

ok 1 number(s): "169678588"

Test #11:

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

input:

500 88888

output:

216149701

result:

ok 1 number(s): "216149701"

Test #12:

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

input:

1000 213456

output:

270989457

result:

ok 1 number(s): "270989457"

Test #13:

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

input:

2000 119988

output:

756425375

result:

ok 1 number(s): "756425375"

Test #14:

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

input:

3000 998244352

output:

71841227

result:

ok 1 number(s): "71841227"

Test #15:

score: 0
Accepted
time: 17ms
memory: 18004kb

input:

3000 555555555

output:

79880116

result:

ok 1 number(s): "79880116"

Test #16:

score: 0
Accepted
time: 12ms
memory: 22684kb

input:

4321 1234

output:

949603993

result:

ok 1 number(s): "949603993"

Test #17:

score: -100
Wrong Answer
time: 4ms
memory: 22496kb

input:

5000 0

output:

6

result:

wrong answer 1st numbers differ - expected: '5', found: '6'