#1889. 数位 DP
数位 DP
数位 DP
题目描述
标题: 数位 DP - Problem - QOJ.ac
#9647. 数位 DP
The problem was used in the following contests:
This problem is prepared by Little09 .
题目背景
小 L 曾经出了这样一个题:
- 给定长度为 4 的整数序列 c,求是否存在长度为 4 的整数序列 a 满足 0≤ai≤ci 且 (((a1anda2)xora3)ora4=m。
小 C 看到后觉得这个数位 DP 题非常板,很没意思。小 L 又修改上述问题的位运算的顺序,出了很多个题。
小 C 忍不了了:“你能不能别再出模板数位 DP 题了?”
小 L 只能把这一堆题交给了你。不过为了增加挑战性,现在你需要对所有可能的 ci 计算出答案并求和。
题目描述
给定长度为 n−1 的字符串 s,对于一个长度为 n 的非负整数序列 a,定义其生成序列 b 为:
-
b1=a1;
-
对于 i>1:
- 若 si−1=A,则 bi=bi−1andai。
- 若 si−1=O,则 bi=bi−1orai。
- 若 si−1=X,则 bi=bi−1xorai。
给定非负整数 k。接下来 q 组询问,每次给定一个 m,求有多少长度为 n 的整数序列 c 满足:
-
对于 1≤i≤n,满足 0≤ci<2k。
-
存在至少一个长度为 n 的整数序列 a 满足:
- 对于 1≤i≤n,满足 0≤ai≤ci。
- 对于 a 的生成序列 b,满足 bn=m。
由于答案很大,你只需要输出答案对 232 取模的结果。
输入格式
第一行三个整数 n,k,q。
第二行一个长度为 n−1 的字符串 s。
接下来 q 行,每行一个询问的 m。
输出格式
输出 q 行,每行一个非负整数,表示答案对 232 取模的结果。
样例
样例输入 #1
3 1 2
OA
0
1
样例输出 #1
8
3
样例输入 #2
4 2 2
XOA
1
2
样例输出 #2
189
112
样例输入 #3
4 2 3
XAO
1
2
3
样例输出 #3
237
176
143
样例输入 #4
10 10 3
AOOXOAOXA
749
666
135
样例输出 #4
4239261913
1948492800
2799056799
提示
本题使用捆绑测试,你只有通过一个子任务的所有测试点,才能获得这个子任务的分数。
子任务编号 n≤ k≤ q≤ 特殊性质 分值 依赖 1 4 5 200 无 10 无 2 20 8 20 无 10 无 3 200 16 1 无 10 无 4 200 16 200 无 10 1,2,3 5 200 30 1 popcount(m)≤16 10 3 6 1000 30 1000 s 不包含 A 10 无 7 50 30 50 无 10 2 8 1000 30 1 无 10 5 9 200 30 200 无 10 4,5,7 10 1000 30 1000 无 10 6,8,9
对于 100 的数据,2≤n≤1000,1≤q≤1000,1≤k≤30,0≤m<2k。
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
3 1 2
OA
0
1
8
3