QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#714948#8080. Pa?sWorDqzez#AC ✓254ms3932kbC++141.4kb2024-11-06 09:23:172024-11-06 09:23:19

Judging History

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

  • [2024-11-06 09:23:19]
  • 评测
  • 测评结果:AC
  • 用时:254ms
  • 内存:3932kb
  • [2024-11-06 09:23:17]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=1e5+10,mod=998244353;
int n,f[2][8][26+26+10];
char a[N];
int trans(char c){
    if(isdigit(c))return c-'0';
    else if(islower(c))return c-'a'+10;
    else return c-'A'+10+26;
}
int get(int i){
    if(i<10)return 0;
    if(i<10+26)return 1;
    return 2;
}
vector<int>p[128];
int main(){
    scanf("%d%s",&n,a+1);
    for(int i=0;i<26;i++){
        p['a'+i]={trans('a'+i),trans('A'+i)};
        p['A'+i]={trans('A'+i)};
        p['?'].push_back(trans('a'+i));
        p['?'].push_back(trans('A'+i));
    }
    for(int i=0;i<10;i++){
        p['0'+i]={trans('0'+i)};
        p['?'].push_back(trans('0'+i));
    }
    // cerr<<p['?'].size()<<endl;
    int now=1,las=0;
    for(int x:p[a[1]])f[now][1<<get(x)][x]=1;
    for(int i=2;i<=n;i++){
        swap(now,las),memset(f[now],0,sizeof f[now]);
        static int sum[8];
        memset(sum,0,sizeof sum);
        for(int S=1;S<8;S++){
            for(int x=0;x<10+26+26;x++){
                (sum[S]+=f[las][S][x])%=mod;
            }
        }
        for(int S=1;S<8;S++){
            for(int y:p[a[i]]){
                (f[now][S|1<<get(y)][y]+=(sum[S]-f[las][S][y]+mod)%mod)%=mod;
            }
        }
    }
    int ans=0;
    for(int x:p['?'])(ans+=f[now][7][x])%=mod;
    cout<<ans<<endl;
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3756kb

input:

4
a?0B

output:

86

result:

ok single line: '86'

Test #2:

score: 0
Accepted
time: 132ms
memory: 3848kb

input:

100000
1kQOIXnSMDlMqJcA8Ae6ov3DfVWAk0I16BgJ3tW1A6ERqBOy4kYizhqPUAU9DrUK26oQ8tgVQW0sRIcg0J2moqS6rRc5lh6QBtzFNfVDvU?sHilmsDIsywXDEeCy8bFracBGSwWNnkLa49E7d9JNXS1QsWPRoYV6IwSvdLdeYMczFmy7G56rxql6YXsX8AaWRLfxqukM5ovPzuSCTpSpN5?OaCE8xb8xu7xJ4A2pOHTOxe1EStiTlWMLeoM5qW6ULwCK4Dtcru8sjqaTilMzLvU27DcJnUhweXT80...

output:

483479164

result:

ok single line: '483479164'

Test #3:

score: 0
Accepted
time: 132ms
memory: 3932kb

input:

100000
hSilkqEibN5P3zsoXdREarzoRC94XflJB6OzigUfyu2ndtAvNBIeRyziL2k7DvqK5zs7O8Mjkw?LP6zyrT7?XLUJCdD7hTkhTmExwPNt58rb1ACY50PRJNBKktdq?m1CMQrFStmBh3DL5Uq2dLaQlByUpjK7gTHC78NclKgCJBrL37F?38KaQ?WVsMWzj4h4HCExAwXAo9M9s71nf0JyAFPs0d4tiPODAFboNfVbSldtpBKTtBznz1kLc7VKGPUkSFvoWEeEWbKQafX5PNEIJ95Xgi4oFeyBVgo4Y...

output:

647474736

result:

ok single line: '647474736'

Test #4:

score: 0
Accepted
time: 179ms
memory: 3724kb

input:

100000
?t?T?1?I?9?L7v?9?q?s?r?BM?n?6?u?M?n0?fR?G?k?s?RB?vwP?7?7?p?Y0?e?M?T?l?UX6?W?n?uz?D?y?x?1?X?z?N?z?O?8?z?j?Rs?D?p?M?91?u?HJrO?U?T?UN?4?yR1?n?xn?7?K?u?kbmz4?6?s?u?m?y?1?1?9?8Uy?1?Pm?0?x?z?E?y?4?F?zlMtF?e7?lF?r4R?4G?6?J?R?b?s4wc?q?L?3?9?N?zD?S?nJ?BaB?e?G?b?LIoP?H?T?vrC?Y?g?H?re?H?s?Qr?s?sGer?J?H?...

output:

955136381

result:

ok single line: '955136381'

Test #5:

score: 0
Accepted
time: 132ms
memory: 3792kb

input:

100000
xapS76EdJv9oTp54DzvJKSpzXq1dOFQL296LzyFdGu17n8QsxIbi8xcS1WlPqgjpJFomTmgX5bd1qysMjEcbF1N3eNGTQDxOo2qhRMSDUdUbmhgN0m5kYVwVGzQO2JIVEbRaO2WOl3qpf3J0XeVxOka3mkx6LOTtl5VndY1SRdHJ8KuKDNxQMPcaDc6frfsxnFADWkvaiMIkltyKGx3b0P6wJwqfD7twvy1DL?gc51otxt6mKG5NnSDsj2mFatU6KR?Ldt2?e3?oBMbztr6q8djvJEXUkSzSo79Qb...

output:

295912606

result:

ok single line: '295912606'

Test #6:

score: 0
Accepted
time: 191ms
memory: 3856kb

input:

100000
?V?k?2?d?u?l?S?1?g?m?8?G?N?J?S?g?DS?y?B?c?1?j?p9?T?i?o?M?S?H?K?L?G?0?w?3?K?b?s?L?Q?a?U?G?t?5?W?8s?H?q?5?p3?Pn?e?B?R?R?E?fM?B?q?R?A?m?W?m?X?i?8?2?Y?e?9?L?q?V?i?n?N?D?t?V?G?S?g?g?7?i?G?O?z?i?C?z?7?3?g?l?l?o?m?K?K?I?nW?c?w?T?o?k?Y?C?I?7?X?z?l?H?rS?9?M?S?s?B?1?T?n?E?C?Y?W?Jf?L?X?y?k?f?1?d?6?c?D?M...

output:

618729923

result:

ok single line: '618729923'

Test #7:

score: 0
Accepted
time: 243ms
memory: 3920kb

input:

100000
?????????????????3?????l???????4??J????????6???C?????G????????????????????????????????h???????????????????????????4???9?????????????????????????6??C????w????????????????????????????????????????E??????8???????????????????????????????F?????????????6???????????????????L?????b???????????????d????...

output:

268229202

result:

ok single line: '268229202'

Test #8:

score: 0
Accepted
time: 204ms
memory: 3776kb

input:

100000
x??T???0D???fmIm?Cqx??q??Pg??Ln?v8?FC?Ur?iv?J???G???D??i??z?????B?6??8xNx???b??Hbvz???????5??9??z???r??h?Hne???G???1z???i???I?DS??Q?Y?????A??c??R???H?X?fO????jaL??Q8z?U??XN??WK?????RO??????r????m4tw????e???K??0?cX?????f?8?W????r?N????d3f??P?w6???v?L??????x???????????????J??????7???TK??N???A??...

output:

110533030

result:

ok single line: '110533030'

Test #9:

score: 0
Accepted
time: 254ms
memory: 3852kb

input:

99983
??????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????...

output:

499883182

result:

ok single line: '499883182'

Test #10:

score: 0
Accepted
time: 131ms
memory: 3856kb

input:

99957
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

442178682

result:

ok single line: '442178682'

Test #11:

score: 0
Accepted
time: 131ms
memory: 3768kb

input:

99962
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

20

result:

ok single line: '20'

Test #12:

score: 0
Accepted
time: 132ms
memory: 3812kb

input:

100000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

10

result:

ok single line: '10'

Test #13:

score: 0
Accepted
time: 135ms
memory: 3932kb

input:

99936
9Wu3ONtzQBv?MfYmPHuTaHBHw5F?N94Q?O3jyi6TBVq7UovgRWcl6hHP?nxPaOA5sUqNVT?mRzEmsKTu?CyVDBlhXY0CHNEhB7bqpF4fkSgLN2En7CI3ml70Q7H1?1?HGunQloFxkqf3RIcf39UoFW2BuNrE1?WPnmVXzG8?57dWnOxA4y6GMv7CRO7nV90fkcbwRPlnm9yD6jrkxJ4afiE7dz7yecGjLPG?G5bITHof10lubr46QEp5?k0sqgSonlJh1XgSvGDn1HC1WDoWm75?cjYsC0wk79ztey...

output:

785373824

result:

ok single line: '785373824'

Test #14:

score: 0
Accepted
time: 134ms
memory: 3736kb

input:

99935
BabABabaAb2Aaba2caBAacAb?7b98c?aCAbBaBbc?ACBbACB?cacC10AbCBAC?AbB?bCAcCbc?3bC7C4Bc0A?bacC4C6Bc56cbacCcABb?B3AB4BAaACBCbaBcAB7AcaCbCaCbcACacBba4bacbcbcaABbBACaAa3C8CACaA6abBc49c4c0bBCaAa3BCcBACBbAbCaCa?ab58Ca3BbC?cb5B1b4AaCAaCAB?B29cCa?ACb3A5bAaABb5a6Bb1AB1CAbabBAaB5CBCbaCabCbBbcb?aCBaA5Aababc?...

output:

20937671

result:

ok single line: '20937671'

Test #15:

score: 0
Accepted
time: 134ms
memory: 3812kb

input:

99976
??AbaBaA8aBaBAB?aBa?6?AB2b2ABA5AB?a?abBabaBa0ABbBA7BAa?bB8aBABABbAaAb6AB6a7aAbB4AababAba?04BAabaA?Bab5AB6?aB6bab5ababBAaAabaBaAaB8A3aA32AbaBAbBaBabB?ba4BAbAB8Aa3ababa8bAbaB1aBAaA2BbB6a0abABAbBb47ABbB3a8Ba0aB7ab?bAa?1aba6aBA2baA18aB34aBAa?9aA4b?bBbaBABaB7AbBa?B0A0baBAbBAB0Ab4aAbabA79AaAbBba5BAb...

output:

258617700

result:

ok single line: '258617700'

Test #16:

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

input:

8
Pa?sWorD

output:

150

result:

ok single line: '150'

Extra Test:

score: 0
Extra Test Passed