QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #769136 | #8834. Formal Fring | int32 | AC ✓ | 43ms | 22520kb | C++14 | 583b | 2024-11-21 16:16:18 | 2024-11-21 16:16:18 |
Judging History
answer
//
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e6+10;
const int mod=998244353;
int n;
int f[N], ans[N];
signed main(){
cin>>n;
f[0]=1;
for(int i=1;i<=n;i++){
if(i&1) f[i]=f[i-1];
else f[i]=(f[i-1]+f[i/2])%mod;
}
ans[0]=1;
for(int i=1;i<=n;i++){
int x=(int)log2(i);
if(i==(1<<x)) ans[i]=1;
else if(i==(1<<(x+1))-1) ans[i]=f[i];
else if(i&1) ans[i]=ans[i-1];
else ans[i]=(ans[i-1]+ans[i/2])%mod;
cout<<ans[i]<<' ';
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 5768kb
input:
10
output:
1 1 2 1 1 3 6 1 1 2
result:
ok 10 numbers
Test #2:
score: 0
Accepted
time: 1ms
memory: 5716kb
input:
70
output:
1 1 2 1 1 3 6 1 1 2 2 5 5 11 26 1 1 2 2 4 4 6 6 11 11 16 16 27 27 53 166 1 1 2 2 4 4 6 6 10 10 14 14 20 20 26 26 37 37 48 48 64 64 80 80 107 107 134 134 187 187 353 1626 1 1 2 2 4 4 6
result:
ok 70 numbers
Test #3:
score: 0
Accepted
time: 43ms
memory: 22520kb
input:
1000000
output:
1 1 2 1 1 3 6 1 1 2 2 5 5 11 26 1 1 2 2 4 4 6 6 11 11 16 16 27 27 53 166 1 1 2 2 4 4 6 6 10 10 14 14 20 20 26 26 37 37 48 48 64 64 80 80 107 107 134 134 187 187 353 1626 1 1 2 2 4 4 6 6 10 10 14 14 20 20 26 26 36 36 46 46 60 60 74 74 94 94 114 114 140 140 166 166 203 203 240 240 288 288 336 336 400 ...
result:
ok 1000000 numbers
Extra Test:
score: 0
Extra Test Passed