QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #811437 | #1085. Brave Seekers of Unicorns | HappyNewDay | AC ✓ | 140ms | 23480kb | C++14 | 1.1kb | 2024-12-12 19:27:30 | 2024-12-12 19:27:31 |
Judging History
answer
#include <bits/stdc++.h>
#define Fst first
#define Snd second
#define MP make_pair
#define ll long long
#define PII pair<int,int>
#define PIL pair<int,ll>
#define PLI pair<ll,int>
#define PLL pair<ll,ll>
#define PDD pair<double,double>
using namespace std;
int n;
ll md=998244353,al=1;
ll d[1000010][2],pre[30][2],prea[2];
int fs[1000010];
int main()
{
scanf("%d",&n); int it=0;
for (int i=1;i<=n;i++)
{
fs[i]=20;
while (!(i&(1<<fs[i]))) fs[i]--;
}
for (int i=1;i<=n;i++)
{
al=(al*2)%md;
for (int j=0;j<2;j++)
{
if (!j) d[i][j]=(d[i][j]+1)%md;
d[i][j]=(d[i][j]+prea[j])%md;
for (int k=0;k<20;k++) if (i&(1<<k)) d[i][j]=(d[i][j]+pre[k][j^1])%md;
//cerr <<i<<" "<<j<<" "<<d[i][j]<<" d\n";
}
while (it<=i && fs[it]<fs[i])
{
for (int j=0;j<2;j++) pre[fs[it]][j]=(pre[fs[it]][j]+d[it][j])%md;
it++;
}
for (int j=0;j<2;j++) prea[j]=(prea[j]+d[i][j])%md;
}
printf("%lld\n",(prea[0]-prea[1]+md)%md); return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3876kb
input:
1
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3888kb
input:
2
output:
3
result:
ok 1 number(s): "3"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3764kb
input:
3
output:
6
result:
ok 1 number(s): "6"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3860kb
input:
5
output:
26
result:
ok 1 number(s): "26"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3896kb
input:
322
output:
782852421
result:
ok 1 number(s): "782852421"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3956kb
input:
10
output:
728
result:
ok 1 number(s): "728"
Test #7:
score: 0
Accepted
time: 0ms
memory: 3772kb
input:
100
output:
234222727
result:
ok 1 number(s): "234222727"
Test #8:
score: 0
Accepted
time: 2ms
memory: 4144kb
input:
10000
output:
348787098
result:
ok 1 number(s): "348787098"
Test #9:
score: 0
Accepted
time: 127ms
memory: 23328kb
input:
1000000
output:
246427510
result:
ok 1 number(s): "246427510"
Test #10:
score: 0
Accepted
time: 123ms
memory: 23472kb
input:
999999
output:
525546416
result:
ok 1 number(s): "525546416"
Test #11:
score: 0
Accepted
time: 125ms
memory: 22628kb
input:
950000
output:
154241852
result:
ok 1 number(s): "154241852"
Test #12:
score: 0
Accepted
time: 124ms
memory: 23480kb
input:
999888
output:
254589934
result:
ok 1 number(s): "254589934"
Test #13:
score: 0
Accepted
time: 140ms
memory: 23336kb
input:
999423
output:
917909701
result:
ok 1 number(s): "917909701"
Test #14:
score: 0
Accepted
time: 74ms
memory: 17108kb
input:
600000
output:
546076071
result:
ok 1 number(s): "546076071"
Test #15:
score: 0
Accepted
time: 0ms
memory: 3852kb
input:
1337
output:
616951443
result:
ok 1 number(s): "616951443"