QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#719869#8543. Periodic SequencezhanghuanruiAC ✓933ms7188kbC++141008b2024-11-07 09:30:532024-11-07 09:30:53

Judging History

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

  • [2024-11-07 09:30:53]
  • 评测
  • 测评结果:AC
  • 用时:933ms
  • 内存:7188kb
  • [2024-11-07 09:30:53]
  • 提交

answer

#include <bits/stdc++.h>
#define int long long
#ifdef zhr_debug
#define debug printf
#else
void debug(const char* s,...){}
#endif
using namespace std;
const int B=500;
void freopen(string file){freopen((file+".in").c_str(),"r",stdin);freopen((file+".out").c_str(),"w",stdout);}
int n,mod;
void add(int &x,int y){x+=y;if(x>=mod)x-=mod;}
void sub(int &x,int y){x-=y;if(x<0)x+=mod;}
int ans[200010];
int dp[200010];
signed main()
{
	cin>>n>>mod;
	for(int i=1;i<=B;i++)
	{
		memset(dp,0,sizeof(dp));dp[i]=1;
		for(int j=i+1;j<=n;j++) add(dp[j],dp[j-1]),add(dp[j],dp[j-1]),sub(dp[j],dp[j-i-1]);
		for(int j=1;j<=n;j++) add(ans[j],dp[j]);
	}
	memset(dp,0,sizeof(dp));
	for(int i=B;i>=0;i--)
	{
		for(int j=B+1;j<=n;j++)
		{
			if(i*j+i+j<=n)
			{
				if(i&1) sub(dp[i*j+i+j],1);
				else add(dp[i*j+i+j],1);
			}
		}
		for(int j=1;j<=n;j++) add(dp[j],dp[j-1]),add(dp[j],dp[j-1]);
	}
	for(int i=1;i<=n;i++) add(ans[i],dp[i]);
	for(int i=1;i<=n;i++) printf("%lld ",ans[i]);
}

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

详细

Test #1:

score: 100
Accepted
time: 18ms
memory: 5352kb

input:

5 1000000007

output:

1 3 6 11 19 

result:

ok 5 number(s): "1 3 6 11 19"

Test #2:

score: 0
Accepted
time: 932ms
memory: 6824kb

input:

200000 567894337

output:

1 3 6 11 19 33 57 100 177 317 573 1045 1919 3547 6592 12311 23091 43479 82153 155715 295983 564049 1077399 2062310 3955185 7598755 14622317 28179337 54379519 105071497 203254163 393607533 195106662 344669981 35619335 477103886 79913732 147415830 329955039 273123672 546045352 337527455 443978690 4597...

result:

ok 200000 numbers

Test #3:

score: 0
Accepted
time: 30ms
memory: 5868kb

input:

2000 1000000009

output:

1 3 6 11 19 33 57 100 177 317 573 1045 1919 3547 6592 12311 23091 43479 82153 155715 295983 564049 1077399 2062310 3955185 7598755 14622317 28179337 54379519 105071497 203254163 393607533 763000999 480458646 875091002 588152874 869906045 159506110 218346934 346224469 716986623 864678016 300921504 68...

result:

ok 2000 numbers

Test #4:

score: 0
Accepted
time: 928ms
memory: 6848kb

input:

200000 998244853

output:

1 3 6 11 19 33 57 100 177 317 573 1045 1919 3547 6592 12311 23091 43479 82153 155715 295983 564049 1077399 2062310 3955185 7598755 14622317 28179337 54379519 105071497 203254163 393607533 763000999 482213802 878601314 596928654 887457605 196364386 290308330 486636949 990790959 401755743 350504783 12...

result:

ok 200000 numbers

Test #5:

score: 0
Accepted
time: 928ms
memory: 7188kb

input:

200000 1000000009

output:

1 3 6 11 19 33 57 100 177 317 573 1045 1919 3547 6592 12311 23091 43479 82153 155715 295983 564049 1077399 2062310 3955185 7598755 14622317 28179337 54379519 105071497 203254163 393607533 763000999 480458646 875091002 588152874 869906045 159506110 218346934 346224469 716986623 864678016 300921504 68...

result:

ok 200000 numbers

Test #6:

score: 0
Accepted
time: 18ms
memory: 5352kb

input:

1 998244853

output:

1 

result:

ok 1 number(s): "1"

Test #7:

score: 0
Accepted
time: 533ms
memory: 6464kb

input:

114514 1009999999

output:

1 3 6 11 19 33 57 100 177 317 573 1045 1919 3547 6592 12311 23091 43479 82153 155715 295983 564049 1077399 2062310 3955185 7598755 14622317 28179337 54379519 105071497 203254163 393607533 763000999 470458656 855091022 538152924 769906145 959506319 818347343 556225268 166988182 844681063 390927468 51...

result:

ok 114514 numbers

Test #8:

score: 0
Accepted
time: 933ms
memory: 6828kb

input:

199998 500000003

output:

1 3 6 11 19 33 57 100 177 317 573 1045 1919 3547 6592 12311 23091 43479 82153 155715 295983 564049 1077399 2062310 3955185 7598755 14622317 28179337 54379519 105071497 203254163 393607533 263000996 480458649 375091005 88152886 369906072 159506173 218347057 346224709 216987088 364678928 300923295 688...

result:

ok 199998 numbers

Extra Test:

score: 0
Extra Test Passed