QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#211776#7400. Digital RootSolitaryDreamWA 3ms16412kbC++173.4kb2023-10-12 21:09:012023-10-12 21:09:02

Judging History

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

  • [2023-10-12 21:09:02]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:16412kb
  • [2023-10-12 21:09:01]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

#define int long long

using pii=pair<int,int>;

const int N=1e6+1e3+7;

int cnt[16][1<<16];

int n,m,B;

char S[N];

int a[N],s[N];

vector<int> pos[16];

int dp[N][2],F[2];

int g[N][2],G[2];

signed main()
{
    scanf("%lld%lld%lld",&n,&m,&B);
    scanf("%s",S+1);
    int cz=0,sz=0,nz=0,bz=0;
    for(int i=1;i<=n;i++)
    {
        if(S[i]=='0')
        {
            for(int j=0;j<2;j++)
                dp[i][j]=dp[i-1][j];
        }
        else
        {
            dp[i][1]=dp[i-1][0];
        }
        dp[i][S[i]!='0']++;
        for(int j=0;j<2;j++)
            F[j]+=dp[i][j];


        if(S[i]=='0')
            sz++;
        else
            sz=0;
        cz+=sz;
        a[i]=islower(S[i])?S[i]-'a'+10:S[i]-'0';
        bz+=a[i]==B-1;
        a[i]%=(B-1);

        
            
        if(S[i]=='0')
        {
            for(int j=0;j<2;j++)
                g[i][j]=g[i-1][j];
        }
        else if(a[i]!=0)
        {
            g[i][1]=g[i-1][0];
        }
        if(S[i]=='0'||a[i]!='0')
            g[i][a[i]!=0]++;
        for(int j=0;j<2;j++)
            G[j]+=g[i][j];
        nz+=S[i]!='0';
    }
    vector<pii>st;
    pos[0].push_back(0);
    int W=B-1;
    for(int i=1;i<=n;i++)
    {
        s[i]=(s[i-1]+a[i])%W;
        pos[s[i]].push_back(i);
        st.push_back({1<<a[i],i});
        for(auto &[x,y]:st)
            x|=1<<a[i];
        vector<pii> nst;
        reverse(st.begin(),st.end());
        for(auto [x,y]:st)
        {
            if(nst.empty()||x!=nst.back().first)
                nst.push_back({x,y});
        }
        st.swap(nst);
        reverse(st.begin(),st.end());
        for(int y=(int)st.size()-1;y>=0;y--)
        {
            int R=st[y].second,L=y>0?st[y-1].second+1:1;
            for(int j=0;j<W;j++)
            {
                int v=(s[i]-j+W)%(W);
                int A=upper_bound(pos[v].begin(),pos[v].end(),R-1)-lower_bound(pos[v].begin(),pos[v].end(),L-1);
                // if(j==2&&A)n
                cnt[j][st[y].first]+=A;
            }
        }
    }
    for(int t=0;t<W;t++)
        for(int i=0;i<W;i++)
            for(int S=0;S<(1<<W);S++)
                if(!(S>>i&1))
                    cnt[t][S^(1<<i)]+=cnt[t][S];
    while(m--)
    {
        scanf("%s",S);
        int x=islower(S[0])?S[0]-'a'+10:S[0]-'0';
        int bx=x;
        x%=W;
        scanf("%s",S);
        if(bx==0)
        {
            int p=strlen(S);
            bool ok=0;
            for(int j=0;j<p;j++)
                if(S[j]=='0')
                    ok=1;
            printf("%lld\n",F[0]+ok*(F[1]));
            continue;
        }
        int p=strlen(S);
        int E=0;
        for(int i=0;i<p;i++)
            E|=1<<(islower(S[i])?S[i]-'a'+10:S[i]-'0');
        long long ans=0;
        ans+=cnt[x][(1<<W)-1];
        if(x==0&&!(E&(1<<W)))
            ans-=F[0];
        if(E&(1<<W))
        {
            E^=(1<<W);
            E|=1;
        }
        else if((E&1)&&!(E&(1<<W)))
        {
            if(x==0)
                ans-=G[1];
        }
        for(int j=0;j<W;j++)
        {
            if(j==x)
                continue;
            int s=(x-j+W)%(W);
            int nS=E>>s|((E<<(W)>>s)&((1<<W)-1));
            nS^=(1<<W)-1;
            ans+=cnt[j][(1<<W)-1]-cnt[j][nS];
        }
        printf("%lld\n",ans);
    }
}

詳細信息

Test #1:

score: 100
Accepted
time: 3ms
memory: 16412kb

input:

9 2 10
123456789
9 12
8 123456789

output:

24
45

result:

ok 2 tokens

Test #2:

score: 0
Accepted
time: 1ms
memory: 11996kb

input:

5 10 5
01234
0 1
1 1
2 1
3 1
4 1
0 1
1 0
2 0
3 0
4 0

output:

1
13
9
9
9
1
10
9
10
6

result:

ok 10 tokens

Test #3:

score: 0
Accepted
time: 0ms
memory: 12080kb

input:

19 6 2
0010111001010011111
0 0
0 1
0 01
1 0
1 1
1 01

output:

42
11
42
179
190
190

result:

ok 6 tokens

Test #4:

score: -100
Wrong Answer
time: 1ms
memory: 12100kb

input:

13 21 3
1010011001002
0 0
0 1
0 10
0 2
0 20
0 21
0 012
1 0
1 1
1 01
1 2
1 20
1 12
1 021
2 0
2 1
2 01
2 2
2 02
2 12
2 102

output:

36
10
36
10
36
10
36
78
90
91
78
78
91
91
58
76
58
91
91
91
91

result:

wrong answer 17th words differ - expected: '76', found: '58'