题目链接：https://codeforces.com/gym/102875/problem/H
题意：t组数据，每组数据都是由一个长度为n的大串和m个小串与m个一点作用都没有的字符组成的，现在要问你在大串能分解成唯一的小串组合。如果可以输出"happymorsecode",如果不能由小串组成，输出"nonono",如果可以分解成很多个小串组合的情况，输出"puppymousecat"与方案数对128取模。
思路:注意到一个细节，那就是m个小串长度在1~5。那么很容易联想到dp，考虑dp[i] 表示以第i位上字母为最后一个小串最后一个字母的方案数。那么对于每个位置我们最多枚举5次就OK了。但是值得注意的是，如果只考虑方案数，很容易出现某个位置dp[j]=0,致使后面出现一大堆0，影响最后的结果，明明是puppymousecat的情况，结果却输出个nonono出来。这说明我们要找个标记，来看有无解的存在。在枚举过程中，每次都需要查询这个字符串是否存在，很容易想到要用map来维护。至此代码也就写出来。

//team yglance+xhwl+TTD
//author: CN.TTDragon
#include<bits/stdc++.h>
typedef long long ll;
const ll mod=128;
const ll maxn=1e5+7;
const double pi=acos(-1);
using namespace std;
int t,n,m;
char ch;//那个没用的字符
string  s;
int len;
string ss;
ll dp[maxn];//记录方案数
ll have[maxn];//1表示只有一个解，0表示确实没有，2表示多个 
map<string , ll > MP;//记录每个小串出现的次数
int main()  
{
    ios::sync_with_stdio(false);
    //freopen("in.in","r",stdin);
    //freopen("mine.out","w",stdout);
    cin>>t;
    while(t--)
    {
        //初始化
        MP.clear();
        memset(dp,0,sizeof(dp));
        memset(have,0,sizeof(have));
        cin>>n>>m;
        for(int i=0;i<m;i++)
        {
            cin>>ch>>s;
            MP[s]++;//对应小串的数量+1
        } 
        cin>>s;//接收大串
        len=s.length();
        s=" "+s;//一开始没有在前面加这个空格，发现操作起来巨麻烦，以至于面向BUG编程了
        dp[0]=1;
        have[0]=1;//这两为什么置1，看完下面就明白
        for(int i=1;i<=len;i++)
        {

            ss="";
            for(int j=i;i-j<=4&&j>=1;j--)
            {
                ss=s[j]+ss;//这个逆序，秀烂我的狗头

                if(MP[ss])//说明这个串是存在的
                {
                    dp[i]+=dp[j-1]*MP[ss];//以这个位置结尾的情况数量增加，ss串是s[i]s[i+1]……s[j] 这个dp[i]需要增加的数量就是dp[j-1]与ss数量的乘积。

                    have[i]+=have[j-1]*MP[ss];//有无解的标记也是同理
                    have[i]=min(have[i],2ll);//注意的是，我们用了0，1，2三种情况表示三种解的情况，这里放回来就好，没必要过大。（关键是自己舒服）
                    dp[i]%=mod;
                } 
            }
        }
//值得注意的是dp[len]=0,不一定代表没有解，这正是have存在的意义
        if(have[len]==0)//最后一位根本不存在解的情况，nonono
        {
            cout<<"nonono"<<endl;
        }
        else if(have[len]==1)//恰好最后一位只有一种情况
        {
            cout<<"happymorsecode"<<endl;
        }
        else//多种情况
        {
            cout<<"puppymousecat "<<dp[len]<<endl;
        }

    }
     return 0;
}

写在最后：看到第一眼，心想字典树，终于能给队伍做贡献了，结果就是一小时时间从T2到T3再到自闭。
雨淋湿了天空 毁的很讲究。