QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#190373 | #1944. Circle of Friends | SolitaryDream# | WA | 17ms | 35808kb | C++20 | 1.5kb | 2023-09-28 19:28:09 | 2023-09-28 19:28:09 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+1e3+7,P=998244353;
int n,a[N];
int f[N],s[N];
int st[21][N];
int qry(int l,int r)
{
int k=__lg(r-l+1);
return st[k][l]&st[k][r-(1<<k)+1];
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n;
vector<int> v;
for(int i=1;i<=n;i++)
{
cin>>a[i];
if(!v.size())
v.push_back(a[i]);
else
{
if((v.back()&a[i])!=v.back())
v.push_back(v.back()&a[i]);
}
}
for(int i=1;i<=n;i++)
st[0][i]=a[i];
for(int j=1;j<=20;j++)
for(int i=1;i+(1<<j)-1<=n;i++)
st[j][i]=(st[j-1][i]&st[j-1][i+(1<<(j-1))]);
int ans=0;
//start from 0
for(int i=1,j=1;i<=n;i++)
{
while(qry(j,i)==0)
j++;
f[i]=(s[i-1]-(j<2?0:s[j-2])+P)%P;
if(qry(1,i)!=0)
f[i]=(f[i]+1)%P;
s[i]=(s[i-1]+f[i])%P;
}
ans=(ans+f[n])%P;
for(auto val:v)
{
if(val==0)
continue;
for(int i=1,j=1;i<=n;i++)
{
f[i]=0;
while(qry(j,i)==0)
j++;
f[i]=(s[i-1]-(j<2?0:s[j-2])+P)%P;
if(qry(1,i)==val)
f[i]=(f[i]+1)%P;
s[i]=(s[i-1]+f[i])%P;
if(i!=n&&((qry(i+1,n)&val)!=0))
ans=(ans+f[i])%P;
}
}
printf("%lld\n",ans);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 7736kb
input:
1 1
output:
1
result:
ok single line: '1'
Test #2:
score: 0
Accepted
time: 1ms
memory: 7768kb
input:
1 1152921504606846975
output:
1
result:
ok single line: '1'
Test #3:
score: -100
Wrong Answer
time: 17ms
memory: 35808kb
input:
200000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...
output:
792253080
result:
wrong answer 1st lines differ - expected: '792053081', found: '792253080'