QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#719869 | #8543. Periodic Sequence | zhanghuanrui | AC ✓ | 933ms | 7188kb | C++14 | 1008b | 2024-11-07 09:30:53 | 2024-11-07 09:30:53 |
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=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