QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #751575 | #8834. Formal Fring | ucup-team1004 | AC ✓ | 125ms | 11708kb | C++17 | 901b | 2024-11-15 19:26:31 | 2024-11-15 19:26:32 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#include"debug.h"
#else
#define debug(...) void()
#endif
#define all(x) (x).begin(),(x).end()
template<class T>
auto ary(T *a,int l,int r){
return vector<T>{a+l,a+1+r};
}
using ll=long long;
using ull=unsigned long long;
const int N=1e6+10,mod=998244353;
int n,f[N],g[N];
int main(){
scanf("%d",&n);
f[0]=1;
for(int k=0;(1<<k)<n;k++){
for(int i=1<<k;i<=n;i++)(f[i]+=f[i-(1<<k)])%=mod;
}
g[0]=1;
for(int i=1;i<=n;i++){
for(int k=0;(1<<k+1)<=i&&i%(1<<k)==0;k++){
g[i]=(g[i]+1ll*g[i-(1<<k+1)>>k]*f[1<<k])%mod;
}
}
for(int i=1;i<=n;i++){
int ans=0;
for(int k=0;(1<<k)<=i;k++){
int x=i%(1<<k),y=i-x-(1<<k),z=(1<<k)-x;
if(__lg(i+z)==__lg(i-z))continue;
ans=(ans+1ll*g[y>>k]*f[x])%mod;
}
printf("%d%c",ans,"\n "[i<n]);
}
return 0;
}
#ifdef DEBUG
#include"debug.hpp"
#endif
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 5952kb
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: 5836kb
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: 125ms
memory: 11708kb
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