前言

其他题目题解点击此处，持续更新……

思路

很明显的动态规划题目，但是我就是想不到，我想到以子序列为dp的目标，但是没有想到以字符串k为dp目标。
多尝试不同的条件，说不定就能碰出火花，不能懒！

记住，动态规划不是一步就达到答案的，是一步一步转化之后才到达答案的。 表示前i个定序列匹配到字符串k第j位的所有合法方案， 所以分为取和不取两种选择，这就类似于01背包了，但是比01背包多了一个点就是取之前需要判断它是否能拼接成字符串k。

所以状态转移方程为 ：
利用滚动数组，将状态转移方程进一步转化为 ：
使用之前的值，所以别忘记了是逆序遍历。

AC代码

#include<bits/stdc++.h>
using namespace std;

#define _for(i, a, b) for (int i = (a); i < (b); ++i)
#define _rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define For(i, a, b) for (int i = (a); i >= (b); --i)
#define mod(x) (x) % 1000000007
#define debug(a) cout << #a << " = " << a << endl;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int N = 5000000 + 10, P = 131, M = 50;
ull p[N], h[N], ha[M];
ll f[N];
int n, len[M];
char k[N], a[M][N];

bool check(ull hash, int l, int r)
{
    return hash == h[r] - h[l - 1] * p[r - l + 1];
}

int main()
{
#ifdef LOCAL
    freopen("data.in", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cout.tie(0);
    cin.tie(0);

    cin >> n >> k + 1;

    int sz = strlen(k + 1);
    p[0] = 1;
    _rep(i, 1, 5e6) {
        p[i] = p[i - 1] * P;
        if (i <= sz) h[i] = h[i - 1] * P + k[i];
    }

    _rep(i, 1, n)
    {
        cin >> a[i] + 1;
        len[i] = strlen(a[i] + 1);
        _rep(j, 1, len[i]) ha[i] = ha[i] * P + a[i][j];
    }

    f[0] = 1;
    _rep(i, 1, n) For(j, sz, len[i]) f[j] += f[j - len[i]] * check(ha[i], j - len[i] + 1, j);
    cout << f[sz] << endl;
    return 0;
}