QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #360371 | #1085. Brave Seekers of Unicorns | SolitaryDream# | AC ✓ | 71ms | 19368kb | C++17 | 720b | 2024-03-21 18:20:46 | 2024-03-21 18:20:48 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int P=998244353,N=1e6+1e3+7;
int n;
int f[N],s[N];
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n;
int ans=0;
for(int i=1;i<=n;i++)
{
int m=__lg(i);
f[i]=(1+s[i-1]+P)%P;
int b=0;
for(int j=m-1;j>=0;j--)
{
if(i>>j&1)
{
f[i]=(f[i]-(s[b+(1<<j+1)-1]-s[b+(1<<j)-1]))%P;
f[i]=(f[i]%P+P)%P;
}
}
s[i]=(s[i-1]+f[i])%P;
// for(int j=1;j<i;j++)
// if((i^j)<j)
// f[i]=(f[i]-f[i^j]+P)%P;
}
cout<<s[n]<<"\n";
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 5724kb
input:
1
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 1ms
memory: 5724kb
input:
2
output:
3
result:
ok 1 number(s): "3"
Test #3:
score: 0
Accepted
time: 0ms
memory: 5780kb
input:
3
output:
6
result:
ok 1 number(s): "6"
Test #4:
score: 0
Accepted
time: 1ms
memory: 5720kb
input:
5
output:
26
result:
ok 1 number(s): "26"
Test #5:
score: 0
Accepted
time: 1ms
memory: 5720kb
input:
322
output:
782852421
result:
ok 1 number(s): "782852421"
Test #6:
score: 0
Accepted
time: 1ms
memory: 5664kb
input:
10
output:
728
result:
ok 1 number(s): "728"
Test #7:
score: 0
Accepted
time: 0ms
memory: 5720kb
input:
100
output:
234222727
result:
ok 1 number(s): "234222727"
Test #8:
score: 0
Accepted
time: 1ms
memory: 5740kb
input:
10000
output:
348787098
result:
ok 1 number(s): "348787098"
Test #9:
score: 0
Accepted
time: 68ms
memory: 19324kb
input:
1000000
output:
246427510
result:
ok 1 number(s): "246427510"
Test #10:
score: 0
Accepted
time: 71ms
memory: 19312kb
input:
999999
output:
525546416
result:
ok 1 number(s): "525546416"
Test #11:
score: 0
Accepted
time: 63ms
memory: 18904kb
input:
950000
output:
154241852
result:
ok 1 number(s): "154241852"
Test #12:
score: 0
Accepted
time: 67ms
memory: 19368kb
input:
999888
output:
254589934
result:
ok 1 number(s): "254589934"
Test #13:
score: 0
Accepted
time: 71ms
memory: 19244kb
input:
999423
output:
917909701
result:
ok 1 number(s): "917909701"
Test #14:
score: 0
Accepted
time: 41ms
memory: 14728kb
input:
600000
output:
546076071
result:
ok 1 number(s): "546076071"
Test #15:
score: 0
Accepted
time: 1ms
memory: 5784kb
input:
1337
output:
616951443
result:
ok 1 number(s): "616951443"