QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#769199#8834. Formal FringdaduoliAC ✓49ms14016kbC++14850b2024-11-21 16:34:292024-11-21 16:34:30

Judging History

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

  • [2024-11-21 16:34:30]
  • 评测
  • 测评结果:AC
  • 用时:49ms
  • 内存:14016kb
  • [2024-11-21 16:34:29]
  • 提交

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