QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #764295 | #8834. Formal Fring | DaiRuiChen007 | WA | 0ms | 3712kb | C++17 | 541b | 2024-11-20 08:32:27 | 2024-11-20 08:32:28 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=1e6+5,MOD=998244353;
int hb(int x) { return 31-__builtin_clz(x); }
int n;
ll f[MAXN];
signed main() {
ios::sync_with_stdio(false);
cin>>n,f[0]=1;
for(int k=1;k<=n;k<<=1) for(int i=k;i<=n;++i) f[i]=(f[i]+f[i-k])%MOD;
cout<<"1 ";
for(int i=2;i<=n;++i) {
int k=hb(i);
if(i==(1<<(k+1))-1) cout<<f[i]<<" ";
else if(i>>(k-1)&1) cout<<(f[i-(1<<k)]+f[i-3*(1<<(k-1))])%MOD<<" ";
else cout<<f[i-(1<<k)]<<" ";
}
cout<<"\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3712kb
input:
10
output:
1 1 2 1 1 3 6 1 1 2
result:
ok 10 numbers
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 3596kb
input:
70
output:
1 1 2 1 1 3 6 1 1 2 2 5 5 8 26 1 1 2 2 4 4 6 6 11 11 16 16 24 24 32 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 104 104 128 128 160 160 192 1626 1 1 2 2 4 4 6
result:
wrong answer 14th numbers differ - expected: '11', found: '8'