在每个序列中都选出一些位置,并将这些位置对应的字符**顺次**拼接起来,采用C语言的程序的设计

Problem Description
光羽一点都不喜欢高代,某一次高代课上,光羽特意挑了最后一排的位置,睡着睡着,他忽然想到了这道字符串水题!

度度熊有k(k≥2)个序列s1,s2,..,sk,每个序列的长度均为n,且序列中每个数均是1到n之间某个整数,请问这k个串有多少个长度大于0的**公共子序列**?

解释:在每个序列中都选出一些位置,并将这些位置对应的字符**顺次**拼接起来,当它们都相等时,称其为公共子序列。

答案可能很大,请对109+7取模。

Input
第一行一个数,表示数据组数T。

每组数据第一行两个数k,n;接下来k行,每行一个长度为n的序列si。

数据组数T=80,分别有20组数据满足k=2,3,4,5。

每组数据均满足1≤n≤1000,**且s1,s2,...,sk中每一个数在1到n之间等概率随机生成!!**

随机生成!!

随机生成!!

随机生成!!

Output
每组数据输出一行,每行仅包含一个数,表示公共子序列个数。

Sample Input
4
2 3
1 2 1
2 3 1
3 3
1 2 3
2 3 1
1 2 3
4 3
3 2 2
3 1 3
2 3 1
3 2 1
5 3
3 1 3
3 1 1
1 2 3
2 3 3
1 3 3

Sample Output
4
4
2
8

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问

相似问题

4
交换二叉树中每个结点的左孩子和右孩子C++语言
2
时间序列数据的预处理问题
13
c语言编译的最大子序列求和问题
1
使用Newtonsoft.Json的JsonConvert.SerializeObject函数序列化字节数组与字符串不匹配
2
一棵非空的二叉树的先序序列和后续序列正好相同,则该二叉树一定满足?
3
怎么样才能获取唯一的CPU序列号
1
定序列A={A1,A2,...,An}, 要求改变序列A中的某些元素,形成一个严格单调的序列B
0
时间序列预测 这种数据应该怎么处理
2
给一个整数x将该数插入到序列中,并使新的序列仍然有序,如何C语言
1
C程序输出题目所要求的序列,序列中每个元素一行。如果存在两个符合要求的序列
3
json字符串反序列化成实体类,新手求解
0
给一个整数x,请将该数插入到序列中,并使新的序列仍然有序,使用C语言怎么实现的计算
0
两个字符串序列的比较的问题,如何利用C语言的方式怎么解决
0
biopython 如何根据另一个txt文件中的序列ID对Fasta文件中的序列进行排序?
0
、请设计一个用于保存和处理DNA序列的类DNASequence,该类具有以下特征和功能:
5
在学习一个猜字符的小游戏,这个break跳出循环的部分怎么理解?
0
求每个序列的排列后最小的总和的一个问题用C语言的实现的办法和具体的过程怎么做
0
请问这个程序用c怎么写?什么时候输出的序列不是单调递增?
2
使用phtread多线程编程程序来生成Fibonacci序列 c/c++
1
python difflib.SequenceMatcher() 字符串序列差异比较