在歌唱王国，所有人的名字都是一个非空的仅包含整数1~n 的字符串。
王国里生活着一大群咕噜兵，他们靠不停的歌唱首领——牛人酋长们的名字
来获取力量。咕噜兵每一次歌唱过程是这样的：
首先，他从整数生成器那儿获得一个数字，然后花一个时间单位将此数字唱
出来，如果他发现某个牛人酋长的名字已经被歌唱出来（即此名字是歌唱序列的
一个连续子串），那么这次歌唱过程就立即结束。
相关名词定义
歌唱序列：如果某人歌唱了x 个数字，第i 次歌唱的数字为ai，那么歌
唱序列=(a1,a2,…,ax)。
整数生成器：歌唱王国的神物，它有一个按钮，如果你按一下按钮，将
从1~n 数字中等概率的随机返回一个整数。
歌唱时间：在一次歌唱过程中花费的时间。
歌唱时间是随机的，无法预料；不过歌唱时间的期望值是固定的，此期望值
即平均来说歌唱时间有多长，亦可称作平均歌唱时间。
王国里的人非常喜欢歌唱，他们希望歌唱的时间越长越好，所以他们决定罢
免一些牛人酋长，使得平均歌唱时间变长。但是他们不能罢免掉所有的牛人酋长，
否则他们每次歌唱都无法停止，无法获取力量；于是他们决定只保留一个牛人酋
长而罢免其余的牛人酋长。
你的任务是：对于给定的n、牛人酋长的个数t 以及每一个牛人酋长的名字，
告诉王国里的人们，对于1≤i≤t，如果保留第i 个牛人酋长，罢免掉其余的，那
么平均歌唱时间将是多少。
提示：此数为一个非负整数！
输出要求：由于这个数字太大，所以你只需输出这个数的末4 位数字。如果
不足4 位，则前面补0(见样例)。
第一行，两个整数n、t；以下t 行描述t 个牛人酋长名字。
文件第i+1(1≤i≤t)行格式如下
第一个数为mi 表示第i 个牛人酋长的名字的长度，在一个空格之后，接
下来有mi 个数，用来描述这个牛人酋长的名字，相邻两个整数之间用一个空
格分开。
共t 行，第i 行为一个整数，表示若保留第i 个牛人酋长而罢免其余的，则平
均歌唱时间最长的末四位数字是多少。
2 2 1 1 3 1 2 1 26 1 6 1 2 3 1 2 3
0002 0010 3352
解释1：
保留第 1 个牛人酋长罢免其余酋长时，一次歌唱结束时可能的歌唱序列为：
"1","2,1","2,2,1","2,2,2,1",……，它们的概率分别为1/2,1/4,1/8,1/16,……，歌唱时
间为1,2,3,4,……。不难证明∑i/2^i=2。
保留第2 个牛人酋长罢免其余酋长时，平均歌唱时间为10。
解释2：
平均歌唱时间为 308933352。
【约定】
1≤n≤10^5，t≤50，1≤mi≤10^5。
有30%的数据满足n≤10^3，mi≤10^3
有50%的数据满足n≤10^4，mi≤10^4
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||