QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#719865#8543. Periodic SequencezhanghuanruiWA 752ms6884kbC++141008b2024-11-07 09:28:352024-11-07 09:28:36

Judging History

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

  • [2024-11-07 09:28:36]
  • 评测
  • 测评结果:WA
  • 用时:752ms
  • 内存:6884kb
  • [2024-11-07 09:28:35]
  • 提交

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=400;
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]);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

5 1000000007

output:

1 3 6 11 19 

result:

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

Test #2:

score: -100
Wrong Answer
time: 752ms
memory: 6884kb

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:

wrong answer 161603rd numbers differ - expected: '417163109', found: '417163110'