QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#799703 | #8080. Pa?sWorD | SGColin | AC ✓ | 188ms | 4076kb | C++20 | 1.6kb | 2024-12-05 17:11:38 | 2024-12-05 17:11:39 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define N 100007
#define mod 998244353
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
char s[N];
int f[62][8], sum[62][8];
void add(int &x, int y) {x = (x + y >= mod ? x + y - mod : x + y);}
int trans(char c) {
if (isdigit(c)) return c - '0'; // 0 - 9
if (islower(c)) return c - 'a' + 10; // 10 - 35
if (isupper(c)) return c - 'A' + 36; // 36 - 61
return -1;
}
int main() {
int n;
scanf("%d", &n);
scanf("%s", s + 1);
if (strlen(s + 1) != n) puts("???");
int x = trans(s[1]);
if (x > 35) f[x][4] = 1;
else if (x > 9) f[x][2] = f[x + 26][4] = 1;
else if (x >= 0) f[x][1] = 1;
else {
rep(j, 0, 9) f[j][1] = 1;
rep(j, 10, 35) f[j][2] = 1;
rep(j, 36, 61) f[j][4] = 1;
}
rep(k, 1, 7)
rep(j, 0, 61) {
sum[j][k] = (j ? sum[j - 1][k] : 0);
add(sum[j][k], f[j][k]);
}
rep(i, 2, n) {
auto dp = [&](int nw, int mask) {
rep(k, 1, 7) {
int tar = sum[61][k] + (nw ? sum[nw - 1][k] : 0) - sum[nw][k];
if (tar < 0) tar += mod;
if (tar >= mod) tar -= mod;
add(f[nw][k | mask], tar);
}
};
memset(f, 0, sizeof(f));
int x = trans(s[i]);
if (x > 35) dp(x, 4);
else if (x > 9) {dp(x, 2); dp(x + 26, 4);}
else if (x >= 0) dp(x, 1);
else {
rep(j, 0, 9) dp(j, 1);
rep(j, 10, 35) dp(j, 2);
rep(j, 36, 61) dp(j, 4);
}
rep(k, 1, 7)
rep(j, 0, 61) {
sum[j][k] = (j ? sum[j - 1][k] : 0);
add(sum[j][k], f[j][k]);
}
bool fl = 0;
rep(k, 1, 7) if (sum[61][k] > 0) fl = true;
if (!fl) printf("%d\n", i);
}
printf("%d\n", sum[61][7]);
return 0;
}
/*
aaaaaaaaA
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3904kb
input:
4 a?0B
output:
86
result:
ok single line: '86'
Test #2:
score: 0
Accepted
time: 83ms
memory: 3892kb
input:
100000 1kQOIXnSMDlMqJcA8Ae6ov3DfVWAk0I16BgJ3tW1A6ERqBOy4kYizhqPUAU9DrUK26oQ8tgVQW0sRIcg0J2moqS6rRc5lh6QBtzFNfVDvU?sHilmsDIsywXDEeCy8bFracBGSwWNnkLa49E7d9JNXS1QsWPRoYV6IwSvdLdeYMczFmy7G56rxql6YXsX8AaWRLfxqukM5ovPzuSCTpSpN5?OaCE8xb8xu7xJ4A2pOHTOxe1EStiTlWMLeoM5qW6ULwCK4Dtcru8sjqaTilMzLvU27DcJnUhweXT80...
output:
483479164
result:
ok single line: '483479164'
Test #3:
score: 0
Accepted
time: 86ms
memory: 4076kb
input:
100000 hSilkqEibN5P3zsoXdREarzoRC94XflJB6OzigUfyu2ndtAvNBIeRyziL2k7DvqK5zs7O8Mjkw?LP6zyrT7?XLUJCdD7hTkhTmExwPNt58rb1ACY50PRJNBKktdq?m1CMQrFStmBh3DL5Uq2dLaQlByUpjK7gTHC78NclKgCJBrL37F?38KaQ?WVsMWzj4h4HCExAwXAo9M9s71nf0JyAFPs0d4tiPODAFboNfVbSldtpBKTtBznz1kLc7VKGPUkSFvoWEeEWbKQafX5PNEIJ95Xgi4oFeyBVgo4Y...
output:
647474736
result:
ok single line: '647474736'
Test #4:
score: 0
Accepted
time: 114ms
memory: 4024kb
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: 86ms
memory: 3948kb
input:
100000 xapS76EdJv9oTp54DzvJKSpzXq1dOFQL296LzyFdGu17n8QsxIbi8xcS1WlPqgjpJFomTmgX5bd1qysMjEcbF1N3eNGTQDxOo2qhRMSDUdUbmhgN0m5kYVwVGzQO2JIVEbRaO2WOl3qpf3J0XeVxOka3mkx6LOTtl5VndY1SRdHJ8KuKDNxQMPcaDc6frfsxnFADWkvaiMIkltyKGx3b0P6wJwqfD7twvy1DL?gc51otxt6mKG5NnSDsj2mFatU6KR?Ldt2?e3?oBMbztr6q8djvJEXUkSzSo79Qb...
output:
295912606
result:
ok single line: '295912606'
Test #6:
score: 0
Accepted
time: 121ms
memory: 4004kb
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: 160ms
memory: 3888kb
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: 133ms
memory: 4032kb
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: 188ms
memory: 4076kb
input:
99983 ??????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????...
output:
499883182
result:
ok single line: '499883182'
Test #10:
score: 0
Accepted
time: 81ms
memory: 4068kb
input:
99957 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
442178682
result:
ok single line: '442178682'
Test #11:
score: 0
Accepted
time: 81ms
memory: 3860kb
input:
99962 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
20
result:
ok single line: '20'
Test #12:
score: 0
Accepted
time: 85ms
memory: 4032kb
input:
100000 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...
output:
10
result:
ok single line: '10'
Test #13:
score: 0
Accepted
time: 87ms
memory: 3892kb
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: 88ms
memory: 4008kb
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: 87ms
memory: 4064kb
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: 3980kb
input:
8 Pa?sWorD
output:
150
result:
ok single line: '150'
Extra Test:
score: 0
Extra Test Passed