QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#719867 | #8543. Periodic Sequence | zhanghuanrui | WA | 563ms | 6884kb | C++14 | 1008b | 2024-11-07 09:30:11 | 2024-11-07 09:30:11 |
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=300;
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]);
}
详细
Test #1:
score: 100
Accepted
time: 14ms
memory: 6264kb
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: 563ms
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 91203rd numbers differ - expected: '239231713', found: '239231714'