QOJ.ac

QOJ

Time Limit: 3 s Memory Limit: 512 MB Total points: 100
[+31]

# 9463. 基础 ABC 练习题

Statistics

题目描述

给定两个集合 S1S2,定义一个长度为 3n 且仅包含 ABC 三种字符的串 s 是好的,当且仅当存在一种方案将 s 划分成 n 个长度为 3 的子序列,且这 n 个子序列都是 ABCBCACAB。设 n 个子序列中 ABC 的个数为 xBCA 的个数为 y,还要求 xS1yS2

现在有一个长度为 3n 的字符串 s,字符串中仅包含 ABC? 四种字符,你需要计算将所有 ? 都分别替换成 ABC 三个字符中的某一个的方案,使得串 s 是好的。

232 取模。

输入格式

本题单个测试点内有多组测试数据。

第一行两个整数 Tid,表示数据组数和子任务编号,保证 T=60id[0,5]id=0 表示是样例。

对于每组数据,第一行一个整数 n

第二行一个长度为 n+1 的 01 串 s1。若 s1 中第 i 个字符为 1,则表示 S1 中含有 i1 这个元素,否则不含。第三行以同样的格式刻画 S2

第四行一个长度为 3n 的字符串 s

对于第 i 组数据,保证 n=i

输出格式

对于每组数据,输出一行一个整数,表示答案。

你可以选择是否回答每组数据,详情见说明部分。

样例

样例输入 1

3 0
1
11
11
ABC
2
101
101
A????C
3
1111
1111
?????????

样例输出 1

1
5
1077

样例解释 1

这个样例不满足 T=60 的限制,仅为理解题意用。

样例 2,3

见下发文件,分别满足子任务 1,2 的性质。

提示与说明

Subtask 分值 特殊限制
1 20 s 中没有 ?,且 |S1|=|S2|=n+1
2 20 s 中没有 ?
3 10 s 中只有 ?,且 |S1|=|S2|=n+1
4 20 |S1|=|S2|=n+1
5 30 无特殊限制

对于所有数据,保证 T=60。对于每个测试点内的第 i 组测试数据,保证 n=i

测试时开启所有合理的子任务依赖。

对于每个测试点内的每组测试数据,如果你不打算回答这组测试数据,请输出 1。否则输出一个整数表示答案。如果格式不正确,不保证能得到对应的分数。

对于每个测试点,会根据你的输出给出你在这组数据上的评分系数 p[0,1]。每个 Subtask 的得分是这个 Subtask 中所有测试点得分系数的最小值乘以这个 Subtask 的分值。

首先,你的程序需要正常结束并且所有你选择回答的答案均正确,否则 p=0

在此基础上,记 d 为在所有数据中你的程序选择回答的最大的 n,则有

p={120dd514+150(d5)5<d15920+3200(d15)15<d3534+1100(d35)35<d60

pd 的大致图像如下图所示。

problem_9463_1.png