P4548 [CTSC2006] 歌唱王国

题目描述

在歌唱王国,所有人的名字都是一个非空的仅包含整数 $1\sim n$ 的字符串。 王国里生活着一大群咕噜兵,他们靠不停地歌唱首领——牛人酋长们的名字来获取力量。咕噜兵每一次歌唱过程是这样的:首先,他从整数生成器那儿获得一个数字,然后花一个时间单位将此数字唱出来,如果他发现某个牛人酋长的名字已经被歌唱出来(即此名字是歌唱序列的一个连续子串),那么这次歌唱过程就立即结束。 相关名词定义: - 歌唱序列:如果某人歌唱了 $x$ 个数字,第 $i$ 次歌唱的数字为 $a_i$,那么歌唱序列 $=(a_1,a_2,\cdots,a_x)$。 - 整数生成器:歌唱王国的神物,它有一个按钮,如果你按一下按钮,将从 $1\sim n$ 数字中等概率的随机返回一个整数。 - 歌唱时间:在一次歌唱过程中花费的时间。 歌唱时间是随机的,无法预料;不过歌唱时间的期望值是固定的,此期望值即平均来说歌唱时间有多长,亦可称作平均歌唱时间。 王国里的人非常喜欢歌唱,他们希望歌唱的时间越长越好,所以他们决定罢免一些牛人酋长,使得平均歌唱时间变长。但是他们不能罢免掉所有的牛人酋长,否则他们每次歌唱都无法停止,无法获取力量;于是他们决定只保留一个牛人酋长而罢免其余的牛人酋长。 你的任务是:对于给定的 $n$、牛人酋长的个数 $t$ 以及每一个牛人酋长的名字,告诉王国里的人们,对于 $1\leq i\leq t$,如果保留第 $i$ 个牛人酋长,罢免掉其余的,那么平均歌唱时间将是多少。 提示:此数为一个非负整数! 输出要求:由于这个数字太大,所以你只需输出这个数的末 $4$ 位数字。如果不足 $4$ 位,则前面补 $0$(见样例)。

输入格式

输出格式

说明/提示

对于 $100\%$ 的数据,$1\leq n\leq 10^5$,$t\leq 50$,$1\leq m_i\leq 10^5$。