QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#764676#8834. Formal FringL_WaveAC ✓81ms19772kbC++201.2kb2024-11-20 10:09:532024-11-20 10:09:54

Judging History

你现在查看的是最新测评结果

  • [2024-11-20 10:09:54]
  • 评测
  • 测评结果:AC
  • 用时:81ms
  • 内存:19772kb
  • [2024-11-20 10:09:53]
  • 提交

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