【百度之星】最强密码

2015年6月8日2,0743
Problem Description

由于近来密码库被盗的现象层出不穷,度度熊决定为自己的账号找一个最强密码。在研究了密码库很久之后,它总结出了一个规律:密码库中的所有密码都是一个“密码生成串”的子序列(某个序列的子序列是从最初序列通过去除某些元素但不破坏余下元素的相对位置(在前或在后)而形成的新序列)。

经过强大的计算集群夜以继日的工作,度度熊得到了这个“密码生成串”。现在它希望找到一个“最强密码”,不是这个“密码生成串”的子序列,并且长度最短。

任性的度度熊还希望知道这样的“最强密码”有多少个。幸运的是,“密码生成串”和“最强密码”都只包含小写字母。

Input

第一行一个整数T,表示T组数据 (1T100)

每组数据包含一个“密码生成串” (100000)

Output

对于每组测试数据输出两行:

第一行输出”Case #i:”,其中 I 代表第 I 组测试数据。

第二行输出两个数,最短长度和该长度的“最强密码”个数(对 1 000 000 007 取模)。用空格分隔。

Sample Input
Sample Output

题解

yy一下构建出一张图,即每个结点加个字母能转移到另一个结点

然后递推一下即可

 

  • 彭柯宾2015年6月11日 下午3:45 回复

    大神,你这个节点是什么意思?求详细解释一下,谢谢啦

    #1  
    • hzwer2015年6月11日 下午4:14 回复
      admin

      当前匹配位置

      #11
      • 彭柯宾2015年6月19日 上午8:53 回复

        哦哦,对的,这个题已经搞懂了,感觉真是神DP,当时比赛的时候没看出来。。。太弱了23333

        #12