QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#714948 | #8080. Pa?sWorD | qzez# | AC ✓ | 254ms | 3932kb | C++14 | 1.4kb | 2024-11-06 09:23:17 | 2024-11-06 09:23:19 |
Judging History
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;
}
详细
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