QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #468129 | #8834. Formal Fring | Purslane | WA | 1ms | 7752kb | C++14 | 820b | 2024-07-08 19:27:45 | 2024-07-08 19:27:45 |
Judging History
answer
#include<bits/stdc++.h>
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=1e6+10,MOD=998244353;
int n,dp[MAXN],hb[MAXN],pre[MAXN];
int main() {
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n;
hb[1]=1;
ffor(i,2,n+2) hb[i]=hb[i>>1]<<1;
dp[0]=pre[0]=1;
ffor(i,1,n) dp[i]=pre[i>>1],pre[i]=(pre[i-1]+dp[i])%MOD;
ffor(i,1,n) {
if(hb[i+1]==i+1) cout<<dp[i]<<' ';
else if(hb[i+2]==i+2) {
if(i==2) cout<<1<<' ';
else cout<<(((dp[i>>1]+(dp[i-hb[i]]-dp[(i-hb[i])>>1])%MOD)%MOD+((dp[i-hb[i]-(hb[i]>>1)]-dp[(i-hb[i]-(hb[i]>>1))>>1])%MOD)%MOD)%MOD+MOD)%MOD<<' ';
}
else if(i&(hb[i]>>1)) {
cout<<(dp[i-hb[i]]+dp[i-hb[i]-(hb[i]>>1)])%MOD<<' ';
}
else cout<<dp[i-hb[i]]<<' ';
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 7752kb
input:
10
output:
1 1 2 1 1 3 6 1 1 2
result:
ok 10 numbers
Test #2:
score: -100
Wrong Answer
time: 1ms
memory: 7684kb
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 24 24 50 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 326 1626 1 1 2 2 4 4 6
result:
wrong answer 28th numbers differ - expected: '27', found: '24'