QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#764676 | #8834. Formal Fring | L_Wave | AC ✓ | 81ms | 19772kb | C++20 | 1.2kb | 2024-11-20 10:09:53 | 2024-11-20 10:09:54 |
Judging History
answer
// Problem: # 8834. Formal Fring
// Author: XZC(L_Wave)
// Language: Cpp/G++20
// Contest:
// URL: https://qoj.ac/problem/8834
// Memory Limit: 1024 MB
// Time Limit: 1000 ms
// Create Time: not 2024-11-20 09:52:28, but 1926-08-17 11:45:14
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = (a), i##ABRACADABRA = (b); i <= i##ABRACADABRA; i++)
#define drep(i, a, b) for (int i = (a), i##ABRACADABRA = (b); i >= i##ABRACADABRA; i--)
using namespace std;
using ll = long long;
constexpr ll mod=998244353;
ll all[1<<20|5],dp[25],hb[1<<20|5];
int n;
int main() {
scanf("%d",&n);
hb[0]=-1,hb[1]=0;
all[0]=1;
rep(i,2,n)hb[i]=hb[i>>1]+1;
for (int i=1;i<=n;i<<=1)rep(S,i,n)(all[S]+=all[S-i])%=mod;
// rep(i,0,n)cout<<all[i]<<'\n';
rep(i,1,19){
dp[i]=all[(1<<i)-1];
drep(j,i-1,1)(dp[i]+=(mod-dp[j])*all[(1<<(i-j))-1])%=mod;
// cout<<i<<' '<<dp[i]<<'\n';
}
rep(S,1,n){
ll res=0;
// cout<<S<<' '<<hb[S]<<'\n';
drep(i,hb[S],0){
if ((~S)>>i&1)break;
(res+=dp[hb[S]-i+1]*all[S&((1<<i)-1)])%=mod;
}
printf("%lld ",res);
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 6012kb
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: 5860kb
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: 81ms
memory: 19772kb
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