QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #458361 | #8834. Formal Fring | ucup-team3586# | AC ✓ | 209ms | 20768kb | C++23 | 1.7kb | 2024-06-29 16:49:54 | 2024-06-29 16:49:55 |
Judging History
answer
//Author: Kevin
#include<bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
#define ll long long
#define ull unsigned ll
#define pb emplace_back
#define mp make_pair
#define ALL(x) (x).begin(),(x).end()
#define rALL(x) (x).rbegin(),(x).rend()
#define srt(x) sort(ALL(x))
#define rev(x) reverse(ALL(x))
#define rsrt(x) sort(rALL(x))
#define sz(x) (int)(x.size())
#define inf 0x3f3f3f3f
#define pii pair<int,int>
#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
#define uni(v) v.resize(unique(ALL(v))-v.begin())
#define longer __int128_t
void die(string S){puts(S.c_str());exit(0);}
const ll mod=998244353;
ll f[1001000];
ll s[1001000];
ll ans[1001000];
ll val[21];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin>>n;
f[0]=s[0]=1;
for(int i=1;i<=n;i++)
{
f[i]=s[i/2];
s[i]=s[i-1]+f[i];
s[i]%=mod;
}
for(int i=1;i<=19;i++)
val[i]=f[(1<<i)-1];
for(int i=1;i<=n;i++)
{
if(i==1)
{
cout<<"1 ";
continue;
}
vector<int> label;
int x=__lg(i);
for(int j=x;j>=0;j--)
label.pb(i>>j&1);
int p=0;
while(p<sz(label)&&label[p]) p++;
vector<ll> dp(p+1);
vector<int> vv(p+1);
for(int i=p;i<sz(label);i++)
if(label[i])
vv[p]^=(1<<(sz(label)-i-1));
for(int i=p;i;i--)
vv[i-1]=vv[i]^(1<<(sz(label)-i));
dp[0]=1;
ll tot=0;
for(int i=0;i<=p;i++)
for(int j=i+1;j<=p;j++)
dp[j]=(dp[j]+mod-dp[i]*val[j-i]%mod)%mod;
for(int i=1;i<=p;i++)
tot=(tot+dp[i]*f[vv[i]])%mod;
cout<<(mod-tot)%mod<<' ';
}
return 0;
}
/*
6
1 1 1 1 1 1
1 1 1 1 2
1 1 2 2
2 2 2
1 1 4
2 4
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 7704kb
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: 7708kb
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: 209ms
memory: 20768kb
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