QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#799703#8080. Pa?sWorDSGColinAC ✓188ms4076kbC++201.6kb2024-12-05 17:11:382024-12-05 17:11:39

Judging History

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

  • [2024-12-05 17:11:39]
  • 评测
  • 测评结果:AC
  • 用时:188ms
  • 内存:4076kb
  • [2024-12-05 17:11:38]
  • 提交

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
*/

详细

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