QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #764318 | #8834. Formal Fring | DaiRuiChen007 | AC ✓ | 68ms | 11456kb | C++17 | 619b | 2024-11-20 08:41:28 | 2024-11-20 08:42:10 |
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],g[24];
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;
for(int i=1;i<20;++i) {
g[i]=f[(1<<i)-1];
for(int j=1;j<i;++j) g[i]=(g[i]+(MOD-g[j])*f[(1<<(i-j))-1])%MOD;
}
for(int i=1;i<=n;++i) {
int k=hb(i),s=0;
for(int j=k;~j;--j) {
if(!(i>>j&1)) break;
s=(s+g[k-j+1]*f[i&((1<<j)-1)])%MOD;
}
cout<<s<<" \n"[i==n];
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3604kb
input:
10
output:
1 1 2 1 1 3 6 1 1 2
result:
ok 10 numbers
Test #2:
score: 0
Accepted
time: 0ms
memory: 3608kb
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: 68ms
memory: 11456kb
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