QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#769199 | #8834. Formal Fring | daduoli | AC ✓ | 49ms | 14016kb | C++14 | 850b | 2024-11-21 16:34:29 | 2024-11-21 16:34:30 |
Judging History
answer
#include<bits/stdc++.h>
#define Yzl unsigned long long
#define fi first
#define se second
#define pi pair<int,int>
#define mp make_pair
#define lob lower_bound
#define pb emplace_back
typedef long long LL;
using namespace std;
const Yzl Lty=20120712;
const int MAXN=(1<<20)+10,P=998244353;
int n,f[MAXN],g[MAXN],h[MAXN];
LL fad(LL x,LL y) {
return (x+y>=P?x+y-P:x+y);
}
int main () {
scanf("%d",&n); f[0]=1;
for(int i=1;i<=n;++i) {
f[i]=fad(f[i-1],(i&1?0:f[i>>1]));
h[i]=(__lg(i)^__lg(i+1)?__lg(i+1):h[i>>1]);
}
for(int i=1;i<=20;++i) {
g[i]=f[(1<<i)-1];
for(int j=1;j<i;++j) g[i]=fad(g[i],(LL)(P-g[j])*f[(1<<(i-j))-1]%P);
}
for(int i=1;i<=n;++i) { LL ans=0;
for(int j=1;j<=h[i];++j) {
ans=fad(ans,(LL)g[j]*f[i^(1<<j)-1<<(__lg(i)-j+1)]%P);
} printf("%lld ",ans);
} puts("");
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 8020kb
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: 8056kb
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: 49ms
memory: 14016kb
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