QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #688929 | #1085. Brave Seekers of Unicorns | 0xyz | AC ✓ | 11ms | 19012kb | C++14 | 501b | 2024-10-30 14:22:06 | 2024-10-30 14:22:08 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int _=1e6+5,p=998244353;
int n,l[_],s[_],f[_],c[_];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n;
s[0]=f[0]=1;l[0]=-1;
for(int i=1,x;i<=n;i++){
l[i]=l[i>>1]+1;x=i^(1<<l[i]);
if(x&&!c[x]){
if(x==(1<<l[x]))c[x]=(s[2*x-1]-s[x-1]+p)%p;
else c[x]=(c[1<<l[x]]+c[x-(1<<l[x])])%p;
}
f[i]=(s[i-1]-c[x]+p)%p;
s[i]=(s[i-1]+f[i])%p;
}
cout<<(s[n]+p-1)%p<<'\n';
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 9804kb
input:
1
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 1ms
memory: 9716kb
input:
2
output:
3
result:
ok 1 number(s): "3"
Test #3:
score: 0
Accepted
time: 1ms
memory: 9816kb
input:
3
output:
6
result:
ok 1 number(s): "6"
Test #4:
score: 0
Accepted
time: 1ms
memory: 9736kb
input:
5
output:
26
result:
ok 1 number(s): "26"
Test #5:
score: 0
Accepted
time: 0ms
memory: 9736kb
input:
322
output:
782852421
result:
ok 1 number(s): "782852421"
Test #6:
score: 0
Accepted
time: 0ms
memory: 9852kb
input:
10
output:
728
result:
ok 1 number(s): "728"
Test #7:
score: 0
Accepted
time: 1ms
memory: 9796kb
input:
100
output:
234222727
result:
ok 1 number(s): "234222727"
Test #8:
score: 0
Accepted
time: 1ms
memory: 9868kb
input:
10000
output:
348787098
result:
ok 1 number(s): "348787098"
Test #9:
score: 0
Accepted
time: 8ms
memory: 18380kb
input:
1000000
output:
246427510
result:
ok 1 number(s): "246427510"
Test #10:
score: 0
Accepted
time: 11ms
memory: 17524kb
input:
999999
output:
525546416
result:
ok 1 number(s): "525546416"
Test #11:
score: 0
Accepted
time: 11ms
memory: 18552kb
input:
950000
output:
154241852
result:
ok 1 number(s): "154241852"
Test #12:
score: 0
Accepted
time: 10ms
memory: 17960kb
input:
999888
output:
254589934
result:
ok 1 number(s): "254589934"
Test #13:
score: 0
Accepted
time: 7ms
memory: 19012kb
input:
999423
output:
917909701
result:
ok 1 number(s): "917909701"
Test #14:
score: 0
Accepted
time: 8ms
memory: 15236kb
input:
600000
output:
546076071
result:
ok 1 number(s): "546076071"
Test #15:
score: 0
Accepted
time: 1ms
memory: 9796kb
input:
1337
output:
616951443
result:
ok 1 number(s): "616951443"