#PQJ1808x9463. QOJ 1808_9463
QOJ 1808_9463
标题: 基础 ABC 练习题 - Problem - QOJ.ac
#9463. 基础 ABC 练习题
题目描述
给定两个集合 S1,S2,定义一个长度为 3n 且仅包含 ABC 三种字符的串 s 是好的,当且仅当存在一种方案将 s 划分成 n 个长度为 3 的子序列,且这 n 个子序列都是 ABC,BCA 或 CAB。设 n 个子序列中 ABC 的个数为 x,BCA 的个数为 y,还要求 x∈S1,y∈S2。
现在有一个长度为 3n 的字符串 s,字符串中仅包含 ABC? 四种字符,你需要计算将所有 ? 都分别替换成 ABC 三个字符中的某一个的方案,使得串 s 是好的。
对 232 取模。
输入格式
本题单个测试点内有多组测试数据。
第一行两个整数 T,id,表示数据组数和子任务编号,保证 T=60,id∈[0,5],id=0 表示是样例。
对于每组数据,第一行一个整数 n。
第二行一个长度为 n+1 的 01 串 s1。若 s1 中第 i 个字符为 1,则表示 S1 中含有 i−1 这个元素,否则不含。第三行以同样的格式刻画 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={120dd≤514+150(d−5)5<d≤15920+3200(d−15)15<d≤3534+1100(d−35)35<d≤60
p 与 d 的大致图像如下图所示。