QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#575817#8080. Pa?sWorDhahahalz#AC ✓74ms3940kbC++205.3kb2024-09-19 16:53:332024-09-19 16:53:35

Judging History

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

  • [2024-09-19 16:53:35]
  • 评测
  • 测评结果：AC
  • 用时：74ms
  • 内存：3940kb
查看
  • [2024-09-19 16:53:33]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define lb long double
const int Max = 2*(int)1e3,mod = 998244353;
int f[2][130][10],presum[10],sum[10],invaild[10];
void solve() {
    int n;cin >> n;
    string s;cin >> s;
    s = " "+ s;
    int t = 0;
    sum[0] = 1;
    for(int i = 1; i <= n; i++,t = 1-t) {
        for(int j = 0; j < 8; j++)presum[j] = sum[j]%mod,sum[j] = 0;
        if((s[i]>='A'&&s[i]<='Z')) {
            for(int k = 0; k <= 128; k++)
                for(int j = 1; j <= 8; j++)f[t][k][j] = 0;
            invaild[0] = 1,invaild[1] = 1,invaild[2] = 1,invaild[3] = 1;
            if(!invaild[4])f[t][s[i]][4] = (presum[0]-f[1-t][s[i]][0]+presum[4]-f[1-t][s[i]][4])%mod,sum[4] += f[t][s[i]][4];
            if(!invaild[5])f[t][s[i]][5] = (presum[1]-f[1-t][s[i]][1]+presum[5]-f[1-t][s[i]][5])%mod,sum[5] += f[t][s[i]][5];
            if(!invaild[6])f[t][s[i]][6] = (presum[2]-f[1-t][s[i]][2]+presum[6]-f[1-t][s[i]][6])%mod,sum[6] += f[t][s[i]][6];
            if(!invaild[7])f[t][s[i]][7] = (presum[3]-f[1-t][s[i]][3]+presum[7]-f[1-t][s[i]][7])%mod,sum[7] += f[t][s[i]][7];
            continue;
        }
        if((s[i]>='0'&&s[i]<='9')) {
            for(int i = 0; i <= 128; i++)
                for(int j = 1; j <= 8; j++)f[t][i][j] = 0;
            invaild[0] = 1,invaild[2] = 1,invaild[4] = 1,invaild[6] = 1;
            if(!invaild[1])f[t][s[i]][1] = (presum[0]-f[1-t][s[i]][0]+presum[1]-f[1-t][s[i]][1])%mod,sum[1] += f[t][s[i]][1];
            if(!invaild[3])f[t][s[i]][3] = (presum[2]-f[1-t][s[i]][2]+presum[3]-f[1-t][s[i]][3])%mod,sum[3] += f[t][s[i]][3];
            if(!invaild[5])f[t][s[i]][5] = (presum[4]-f[1-t][s[i]][4]+presum[5]-f[1-t][s[i]][5])%mod,sum[5] += f[t][s[i]][5];
            if(!invaild[7])f[t][s[i]][7] = (presum[6]-f[1-t][s[i]][6]+presum[7]-f[1-t][s[i]][7])%mod,sum[7] += f[t][s[i]][7];
            continue;
        }
        if((s[i]>='a'&&s[i]<='z')) {
            for(int i = 0; i <= 128; i++)
                for(int j = 1; j <= 8; j++)f[t][i][j] = 0;
            invaild[0] = 1,invaild[1] = 1;
            if(!invaild[2])f[t][s[i]][2] = (presum[0]-f[1-t][s[i]][0]+presum[2]-f[1-t][s[i]][2])%mod,sum[2] += f[t][s[i]][2];
            if(!invaild[3])f[t][s[i]][3] = (presum[1]-f[1-t][s[i]][1]+presum[3]-f[1-t][s[i]][3])%mod,sum[3] += f[t][s[i]][3];
            if(!invaild[6])f[t][s[i]][6] = (presum[4]-f[1-t][s[i]][4]+presum[6]-f[1-t][s[i]][6])%mod,sum[6] += f[t][s[i]][6];
            if(!invaild[7])f[t][s[i]][7] = (presum[5]-f[1-t][s[i]][5]+presum[7]-f[1-t][s[i]][7])%mod,sum[7] += f[t][s[i]][7];
            s[i] = s[i]-'a'+'A';
            if(!invaild[4])f[t][s[i]][4] = (presum[0]-f[1-t][s[i]][0]+presum[4]-f[1-t][s[i]][4])%mod,sum[4] += f[t][s[i]][4];
            if(!invaild[5])f[t][s[i]][5] = (presum[1]-f[1-t][s[i]][1]+presum[5]-f[1-t][s[i]][5])%mod,sum[5] += f[t][s[i]][5];
            if(!invaild[6])f[t][s[i]][6] = (presum[2]-f[1-t][s[i]][2]+presum[6]-f[1-t][s[i]][6])%mod,sum[6] += f[t][s[i]][6];
            if(!invaild[7])f[t][s[i]][7] = (presum[3]-f[1-t][s[i]][3]+presum[7]-f[1-t][s[i]][7])%mod,sum[7] += f[t][s[i]][7];
            continue;
        }
        for(s[i] = (int)'0'; (int)s[i] < 127; s[i] = (char)(s[i]+1)) {
            if((s[i]>='A'&&s[i]<='Z')) {
                if(!invaild[4])f[t][s[i]][4] = (presum[0]-f[1-t][s[i]][0]+presum[4]-f[1-t][s[i]][4])%mod,sum[4] += f[t][s[i]][4];
                if(!invaild[5])f[t][s[i]][5] = (presum[1]-f[1-t][s[i]][1]+presum[5]-f[1-t][s[i]][5])%mod,sum[5] += f[t][s[i]][5];
                if(!invaild[6])f[t][s[i]][6] = (presum[2]-f[1-t][s[i]][2]+presum[6]-f[1-t][s[i]][6])%mod,sum[6] += f[t][s[i]][6];
                if(!invaild[7])f[t][s[i]][7] = (presum[3]-f[1-t][s[i]][3]+presum[7]-f[1-t][s[i]][7])%mod,sum[7] += f[t][s[i]][7];
                continue;
            }
            if((s[i]>='0'&&s[i]<='9')) {
                if(!invaild[1])f[t][s[i]][1] = (presum[0]-f[1-t][s[i]][0]+presum[1]-f[1-t][s[i]][1])%mod,sum[1] += f[t][s[i]][1];
                if(!invaild[3])f[t][s[i]][3] = (presum[2]-f[1-t][s[i]][2]+presum[3]-f[1-t][s[i]][3])%mod,sum[3] += f[t][s[i]][3];
                if(!invaild[5])f[t][s[i]][5] = (presum[4]-f[1-t][s[i]][4]+presum[5]-f[1-t][s[i]][5])%mod,sum[5] += f[t][s[i]][5];
                if(!invaild[7])f[t][s[i]][7] = (presum[6]-f[1-t][s[i]][6]+presum[7]-f[1-t][s[i]][7])%mod,sum[7] += f[t][s[i]][7];
                continue;
            }
            if((s[i]>='a'&&s[i]<='z')) {
                if(!invaild[2])f[t][s[i]][2] = (presum[0]-f[1-t][s[i]][0]+presum[2]-f[1-t][s[i]][2])%mod,sum[2] += f[t][s[i]][2];
                if(!invaild[3])f[t][s[i]][3] = (presum[1]-f[1-t][s[i]][1]+presum[3]-f[1-t][s[i]][3])%mod,sum[3] += f[t][s[i]][3];
                if(!invaild[6])f[t][s[i]][6] = (presum[4]-f[1-t][s[i]][4]+presum[6]-f[1-t][s[i]][6])%mod,sum[6] += f[t][s[i]][6];
                if(!invaild[7])f[t][s[i]][7] = (presum[5]-f[1-t][s[i]][5]+presum[7]-f[1-t][s[i]][7])%mod,sum[7] += f[t][s[i]][7];

            }
        }

    }
    sum[7]%=mod;
    if(sum[7]<0)sum[7]+=mod;
    cout << sum[7];
}
 signed main() {
#ifdef ACM_LOCAL
    freopen("data.in","r",stdin);
    freopen("data.out","w",stdout);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t=1;
    //cin>>t;
    while(t--) {
        solve();
    }
}
源文件, 语言: C++20

详细

Test #1:

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

input:

4
a?0B

output:

86

result:

ok single line: '86'

Test #2:

score: 0
Accepted
time: 17ms
memory: 3940kb

input:

100000
1kQOIXnSMDlMqJcA8Ae6ov3DfVWAk0I16BgJ3tW1A6ERqBOy4kYizhqPUAU9DrUK26oQ8tgVQW0sRIcg0J2moqS6rRc5lh6QBtzFNfVDvU?sHilmsDIsywXDEeCy8bFracBGSwWNnkLa49E7d9JNXS1QsWPRoYV6IwSvdLdeYMczFmy7G56rxql6YXsX8AaWRLfxqukM5ovPzuSCTpSpN5?OaCE8xb8xu7xJ4A2pOHTOxe1EStiTlWMLeoM5qW6ULwCK4Dtcru8sjqaTilMzLvU27DcJnUhweXT80...

output:

483479164

result:

ok single line: '483479164'

Test #3:

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

input:

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

output:

647474736

result:

ok single line: '647474736'

Test #4:

score: 0
Accepted
time: 25ms
memory: 3772kb

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: 17ms
memory: 3940kb

input:

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

output:

295912606

result:

ok single line: '295912606'

Test #6:

score: 0
Accepted
time: 24ms
memory: 3752kb

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: 35ms
memory: 3752kb

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: 31ms
memory: 3688kb

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: 74ms
memory: 3908kb

input:

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

output:

499883182

result:

ok single line: '499883182'

Test #10:

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

input:

99957
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

442178682

result:

ok single line: '442178682'

Test #11:

score: 0
Accepted
time: 18ms
memory: 3684kb

input:

99962
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

20

result:

ok single line: '20'

Test #12:

score: 0
Accepted
time: 18ms
memory: 3700kb

input:

100000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

10

result:

ok single line: '10'

Test #13:

score: 0
Accepted
time: 18ms
memory: 3680kb

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: 18ms
memory: 3936kb

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: 18ms
memory: 3680kb

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: 3552kb

input:

8
Pa?sWorD

output:

150

result:

ok single line: '150'

Extra Test:

score: 0
Extra Test Passed
English 繁體中文 简体中文

服务器时间: 2025-02-01 13:50:05 | 开源项目