#PQJ2602x15049. QOJ 2602_15049
QOJ 2602_15049
2018 陕西省青少年信息学(计算机)奥林匹克集训队试题2 2018 年4 月22 日 宝宝的难题 题目描述 王保保有一个孩子,名字叫王宝宝。王宝宝从小就聪明,喜欢鄙视自己的父亲,有一天, 他又想出来一道题目,拿来给王保保看,王保保自然是做不出来的,所以来请教各位了。 题目是这样的: 给定N 个长度为K 的字符串S[1]~S[N]。 S[1][1],S[1][2],S[1][3],...,S[1][K] S[2][1],S[2][2],S[2][3],...,S[2][K] ... S[N][1],S[N][2],S[N][3],...,S[N][K] 你需要从每一个字符串中,选择一个位置W[i],然后,按照下列顺序输出一个字符串: Step1:按照初始时候W[i]从小到大的顺序(如果W[i]相同则按照i 从小到大的顺序), 输出每一个字符串第W[i]位。 Step2:重复Step1 K 次。 例如: S[1]=abcde S[2]=fghij S[3]=zzzzz W[1]=2,W[2]=0,W[3]=0 那么,输出的字符串是: fzcgzdhzeizajzb 现在,我们的问题是:给定N,K,以及这N 个字符串,我们有多少种选择W[i]的方法 使得最终输出的字符串等于T。 输入格式 第一行输入N,K,含义如题意所示。 第二行输入一个字符串T,表示目标字符串,保证T 的长度等于N*K。 接下来N 行,每行一个长度为K 的字符串,表示S[1]~S[N]。 输出格式 一个整数,表示答案。 输入样例 3 3 abaabaaba aaa aaa bbb 输出样例 8 样例解释: 一共八种情况, W[1]=0,W[2]=1,W[3]=0 W[1]=0,W[2]=2,W[3]=0 W[1]=1,W[2]=0,W[3]=0
2018 陕西省青少年信息学(计算机)奥林匹克集训队试题2
2018 年4 月22 日
W[1]=2,W[2]=0,W[3]=0
W[1]=0,W[2]=2,W[3]=1
W[1]=2,W[2]=0,W[3]=1
W[1]=1,W[2]=2,W[3]=1
W[1]=2,W[2]=1,W[3]=1
数据范围
case
n
k
ans
1
<=5
<=15
2
3
10
<=2000000
4
<=15
5
6
7
<=20000000
8
9
10