QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#719857 | #8543. Periodic Sequence | zhanghuanrui | WA | 752ms | 6884kb | C++14 | 1008b | 2024-11-07 09:25:45 | 2024-11-07 09:25:45 |
Judging History
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 i=1;i<=n;i++) add(dp[i],dp[i-1]),add(dp[i],dp[i-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: 14ms
memory: 5292kb
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'