QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#190373#1944. Circle of FriendsSolitaryDream#WA 17ms35808kbC++201.5kb2023-09-28 19:28:092023-09-28 19:28:09

Judging History

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

  • [2023-09-28 19:28:09]
  • 评测
  • 测评结果:WA
  • 用时:17ms
  • 内存:35808kb
  • [2023-09-28 19:28:09]
  • 提交

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'