QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#305168#8009. Growing SequenceszhouhuanyiAC ✓1ms3976kbC++201.9kb2024-01-14 19:47:372024-01-14 19:47:37

Judging History

This is the latest submission verdict.

  • [2024-01-14 19:47:37]
  • Judged
  • Verdict: AC
  • Time: 1ms
  • Memory: 3976kb
  • [2024-01-14 19:47:37]
  • Submitted

answer

#include<iostream>
#include<cstdio>
#define N 60
#define mod 998244353
using namespace std;
long long read()
{
	char c=0;
	long long sum=0;
	while (c<'0'||c>'9') c=getchar();
	while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
	return sum;
}
int MD(int x)
{
	return x>=mod?x-mod:x;
}
int MD2(int x)
{
	return x<0?x+mod:x;
}
void Adder(int &x,int d)
{
	x+=d;
	if (x>=mod) x-=mod;
	return;
}
void Adder2(int &x,int d)
{
	x+=d;
	if (x<0) x+=mod;
	return;
}
int n,ans,dp[N+1][N+1],F[N+1],G[N+1],pw2[N+1],inv[N+1],C[N+1][N+1],S[N+1][N+1],S2[N+1][N+1];
long long c;
int main()
{
	pw2[0]=1;
	for (int i=1;i<=N;++i) pw2[i]=2ll*pw2[i-1]%mod;
	inv[1]=1;
	for (int i=2;i<=N;++i) inv[i]=MD2(-1ll*(mod/i)*inv[mod%i]%mod);
	for (int i=0;i<=N;++i) C[i][0]=1;
	for (int i=1;i<=N;++i)
		for (int j=1;j<=i;++j)
			C[i][j]=MD(C[i-1][j-1]+C[i-1][j]);
	S[0][0]=S2[0][0]=1;
	for (int i=1;i<=N;++i)
		for (int j=1;j<=i;++j)
			S[i][j]=MD(S[i-1][j-1]+1ll*S[i-1][j]*(i-1)%mod),S2[i][j]=MD(S2[i-1][j-1]+1ll*S2[i-1][j]*j%mod);
	n=read(),c=read()-(1ll<<(n-1));
	if (c<0)
	{
		puts("0");
		return 0;
	}
	dp[0][0]=dp[0][1]=1;
	for (int i=1;i<=n-1;++i)
	{
		for (int j=0;j<=i;++j) F[j]=G[j]=0;
		if ((c>>(i-1))&1)
		{
			for (int j=0;j<=i;++j)
				for (int k=0;k<=j;++k)
					Adder(F[k],1ll*dp[i-1][j]*C[j][k]%mod*pw2[k]%mod);
		}
		else
		{
			for (int j=0;j<=i;++j) F[j]=1ll*dp[i-1][j]*pw2[j]%mod;
		}
		for (int j=0;j<=i;++j)
			for (int k=0;k<=j;++k)
				Adder(G[k],1ll*F[j]*S2[j][k]%mod);
		for (int j=i+1;j>=1;--j) Adder(G[j],1ll*G[j-1]*inv[j]%mod);
		for (int j=0;j<=i+1;++j)
			for (int k=0;k<=j;++k)
			{
				if (!((j-k)&1)) Adder(dp[i][k],1ll*G[j]*S[j][k]%mod);
				else Adder2(dp[i][k],-1ll*G[j]*S[j][k]%mod);
			}
	}
	c/=(1ll<<(n-1));
	for (int i=0,res=1;i<=n;++i,res=1ll*res*(c%mod)%mod) Adder(ans,1ll*dp[n-1][i]*res%mod);
	printf("%d\n",ans);
	return 0;
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

1 5

output:

5

result:

ok answer is '5'

Test #2:

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

input:

3 6

output:

4

result:

ok answer is '4'

Test #3:

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

input:

15 179

output:

0

result:

ok answer is '0'

Test #4:

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

input:

35 1234567887654321

output:

576695683

result:

ok answer is '576695683'

Test #5:

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

input:

45 228228228

output:

0

result:

ok answer is '0'

Test #6:

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

input:

60 576460752303423487

output:

0

result:

ok answer is '0'

Test #7:

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

input:

60 576460752303423488

output:

1

result:

ok answer is '1'

Test #8:

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

input:

1 1000000000000000000

output:

716070898

result:

ok answer is '716070898'

Test #9:

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

input:

1 1

output:

1

result:

ok answer is '1'

Test #10:

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

input:

15 1

output:

0

result:

ok answer is '0'

Test #11:

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

input:

1 964573170374708959

output:

695628865

result:

ok answer is '695628865'

Test #12:

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

input:

2 336

output:

28224

result:

ok answer is '28224'

Test #13:

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

input:

5 463

output:

172916212

result:

ok answer is '172916212'

Test #14:

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

input:

7 75427

output:

523581579

result:

ok answer is '523581579'

Test #15:

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

input:

10 28166

output:

145818175

result:

ok answer is '145818175'

Test #16:

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

input:

12 77890

output:

724302124

result:

ok answer is '724302124'

Test #17:

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

input:

3 401245

output:

68076875

result:

ok answer is '68076875'

Test #18:

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

input:

8 511955

output:

109524351

result:

ok answer is '109524351'

Test #19:

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

input:

15 484969

output:

99426993

result:

ok answer is '99426993'

Test #20:

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

input:

30 779369

output:

0

result:

ok answer is '0'

Test #21:

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

input:

17 638679755

output:

132031375

result:

ok answer is '132031375'

Test #22:

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

input:

25 669522429

output:

896585516

result:

ok answer is '896585516'

Test #23:

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

input:

29 748278478

output:

563047844

result:

ok answer is '563047844'

Test #24:

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

input:

33 642978862039931

output:

550967529

result:

ok answer is '550967529'

Test #25:

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

input:

38 218051542638139

output:

29411033

result:

ok answer is '29411033'

Test #26:

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

input:

44 188775063557057

output:

185410072

result:

ok answer is '185410072'

Test #27:

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

input:

48 4677253159871213

output:

863467586

result:

ok answer is '863467586'

Test #28:

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

input:

22 854279883518523144

output:

916505804

result:

ok answer is '916505804'

Test #29:

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

input:

38 730620861826239715

output:

433138392

result:

ok answer is '433138392'

Test #30:

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

input:

54 435826341367976434

output:

237455633

result:

ok answer is '237455633'

Test #31:

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

input:

55 536518888651224157

output:

665085880

result:

ok answer is '665085880'

Test #32:

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

input:

56 413839394784728775

output:

647247529

result:

ok answer is '647247529'

Test #33:

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

input:

57 514531937773009201

output:

425329246

result:

ok answer is '425329246'

Test #34:

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

input:

58 391852448201481116

output:

522300883

result:

ok answer is '522300883'

Test #35:

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

input:

59 492544995484728838

output:

937899244

result:

ok answer is '937899244'

Test #36:

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

input:

60 693597573066212298

output:

490610488

result:

ok answer is '490610488'

Test #37:

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

input:

60 1000000000000000000

output:

13328531

result:

ok answer is '13328531'

Extra Test:

score: 0
Extra Test Passed