QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #766433 | #8834. Formal Fring | byron10000 | AC ✓ | 101ms | 21788kb | C++14 | 1.3kb | 2024-11-20 17:18:30 | 2024-11-20 17:18:34 |
Judging History
answer
#if defined(_USE_PCH_)
#include "pch.hpp"
#else
#include <bits/stdc++.h>
#endif
#define RNG(V_, A_, B_, ...) for(int V_=(A_), V_##_END=(B_) __VA_OPT__(,) __VA_ARGS__; V_<=V_##_END; V_++)
#define IRNG(V_, A_, B_, ...) for(int V_=(A_), V_##_END=(B_) __VA_OPT__(,) __VA_ARGS__; V_>=V_##_END; V_--)
#ifdef _WIN32
#define long int64_t
#endif
#define fi first
#define se second
#define _UN using namespace
using namespace std;
typedef pair<int,int> pii;
typedef __int128 i128;
const int MAXN=1<<21; const int MOD=998244353;
void addto(long& x,long y){ x=(x+y+MOD)%MOD; }
int n;
long F[MAXN],G[MAXN];
int main(){
#if defined(_LOCAL_)
freopen("in","r",stdin);
// freopen("out","w",stdout);
// freopen("/dev/null","w",stderr);
#else
// freopen("0.in","r",stdin);
// freopen("0.out","w",stdout);
#endif
ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
cin>>n;
F[0]=1;
RNG(t,0,__lg(n)){
RNG(i,1<<t,n) addto(F[i],F[i-(1<<t)]);
}
RNG(i,1,n,t=0){
if((1<<(t+1))<=i) t++;
if((1<<t)==i){
fill_n(G,1<<(t+1),0),G[0]=1;
IRNG(s,t,0){
RNG(j,1<<s,(1<<(t+1))-2*(1<<s)) addto(G[j],G[j-(1<<s)]);
}
}
cout<<(F[i]-G[i]+MOD)%MOD<<" ";
}
cout<<"\n";
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5656kb
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: 5728kb
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: 101ms
memory: 21788kb
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