版权声明：转载请注明出处。 https://blog.csdn.net/u014427196/article/details/47128151

题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=5318

题意：
给你n种串。，每种无限个，选择m个物品，问你可以组成几种串。
如果a串的后缀和b串的前缀相等，并且长度>=2，则b串可以连在a串后面（注意，不用合并a，b串相同的位置）。

思路：输入的字符串可能有相同的，注意去重。
若s[i]，s[j]可以链接，则ok[i][j] = 1 ; 否则为 0 ；

定义dp[i][j] 表示选择i个串，一、以j串结尾的方案数。
则dp[i][j] = dp[i-1][k]*ok[k][j] (1<= k <= n)

res矩阵第一行初使为1，其他为 0 .

代码：

#include <stdio.h>
#include <ctime>
#include <math.h>
#include <limits.h>
#include <complex>
#include <string>
#include <functional>
#include <iterator>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <list>
#include <bitset>
#include <sstream>
#include <iomanip>
#include <fstream>
#include <iostream>
#include <ctime>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <time.h>
#include <ctype.h>
#include <string.h>
#include <string>
#include <assert.h>

using namespace std;

int n, m;
const int MOD = 1000000007;

struct node
{
    int ok[55][55];
}is;

node multi(node a, node b)
{
    node tmp;
    memset(tmp.ok,0,sizeof(tmp.ok));
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            for (int k = 1; k <= n; k++)
            {
                tmp.ok[i][j] += ((long long)a.ok[i][k] * (long long)b.ok[k][j]) % MOD;
                tmp.ok[i][j] %= MOD;
            }
    return tmp;
}

//////////////////
char s[100][20];

bool check(int x, int y) //判断是否符合前缀 后缀要求
{
    int lenx = strlen(s[x]), leny = strlen(s[y]);
    if (lenx == 1 || leny == 1) return false;
    for (int i = lenx - 2; i >= 0; i--) 
    {
        int j = 0, ti = i;
        while (ti < lenx && j < leny && s[x][ti] == s[y][j]) ti++, j++;
        if (ti == lenx) return true;
    }
    return false;
}

void solve()
{
    int tm = m;
    node tmp = is, res;
    memset(res.ok, 0, sizeof(res.ok));
    for (int i = 1; i <= n; i++) res.ok[1][i] = 1;

    tm--;
    while (tm)
    {
        if (tm & 1)
            res = multi(res,tmp);
        tmp = multi(tmp, tmp);
        tm >>= 1;
    }
    int ans = 0;
    for (int i = 1; i <= n; i++)
        ans = (ans + res.ok[1][i]) % MOD;
    printf("%d\n",ans);
}

set<string> vec;

int main()
{
    int t;
    scanf("%d",&t);
    while (t--)
    {
        memset(is.ok, 0, sizeof(is.ok));
        vec.clear();
        scanf("%d%d", &n, &m);

        for (int i = 1; i <= n; i++)
        {
            scanf("%s",s[i]);
            vec.insert(s[i]);
        }
        int num = 0;
        for (auto &it : vec) strcpy(s[++num],it.c_str());
        n = num;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                if (check(i, j)) is.ok[i][j] = 1;
        solve();
    }
    return 0;
}