[USACO19JAN]Cow Poetry

题面

Solution:

这是一道很好的dp题。

一开始看不懂题面没有一点思路，看了好久题解才看懂题目...

\(y[i]\) 为第 \(i\) 个词结尾，\(l[i]\) 为第 \(i\) 个词长度。

设状态 \(f[i][j]\) 为长度为 \(i\) 的，以 \(j\) 结尾的一句诗的方案数，那么

\[f[i][Y] = \sum_{y[i]=Y}\sum_{x=1}^{n}f[i-l[j]][x]
\]

发现后面那一坨可以预处理，设

\[g[i]=\sum_{x=1}^nf[i][x]
\]

\(g[i]\) 的意义是长度为 \(i\) 一句诗的方案数，显然可以无限背包 \(O(nk)\) 求。

\[g[i]=\sum_{j=1}^ng[i-l[j]]
\]

那么

\[f[i][Y]=\sum_{y[j]=Y}g[i-l[j]]
\]

对于每一个需要押的韵('A','B'...)答案就等于：

\[Ans[i] = \sum_{j=1}^nf[k][j]^{cnt[i]}
\]

然后输出 \(\prod_\limits{i=A}^ZAns[i]\)。

\(Source:\)

#include <set>

#include <cmath>

#include <cctype>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <assert.h>

#include <algorithm>

using namespace std;

#define fir first

#define sec second

#define pb push_back

#define mp make_pair

#define LL long long

#define INF (0x3f3f3f3f)

#define mem(a, b) memset(a, b, sizeof (a))

#define debug(...) fprintf(stderr, __VA_ARGS__)

#define Debug(x) cout << #x << " = " << x << endl

#define travle(i, x) for (register int i = head[x]; i; i = nxt[i])

#define For(i, a, b) for (register int (i) = (a); (i) <= (b); ++ (i))

#define Forr(i, a, b) for (register int (i) = (a); (i) >= (b); -- (i))

#define file(s) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)

#define ____ debug("go\n")

namespace io {

    static char buf[1<<21], *pos = buf, *end = buf;

    inline char getc()

    { return pos == end && (end = (pos = buf) + fread(buf, 1, 1<<21, stdin), pos == end) ? EOF : *pos ++; }

    inline int rint() {

        register int x = 0, f = 1;register char c;

        while (!isdigit(c = getc())) if (c == '-') f = -1;

        while (x = (x << 1) + (x << 3) + (c ^ 48), isdigit(c = getc()));

        return x * f;

    }

    inline LL rLL() {

        register LL x = 0, f = 1; register char c;

        while (!isdigit(c = getc())) if (c == '-') f = -1;

        while (x = (x << 1ll) + (x << 3ll) + (c ^ 48), isdigit(c = getc()));

        return x * f;

    }

    inline void rstr(char *str) {

        while (isspace(*str = getc()));

        while (!isspace(*++str = getc()))

            if (*str == EOF) break;

        *str = '\0';

    }

    template<typename T>

        inline bool chkmin(T &x, T y) { return x > y ? (x = y, 1) : 0; }

    template<typename T>

        inline bool chkmax(T &x, T y) { return x < y ? (x = y, 1) : 0; }

}

using namespace io;

const int N = 5e3 + 1, mod = 1e9 + 7;

int f[N][N], g[N], cnt[N], y[N], l[N], n, m, k;

LL qpow(LL a, LL b) {

    LL res = 1;

    while (b) {

        if (b & 1) res = res * a % mod;

        a = a * a % mod;

        b >>= 1;

    }

    return res;

}

int main() {

#ifndef ONLINE_JUDGE

    file("Cow_Poetry");

#endif

    n = rint(), m = rint(), k = rint();

    for (register int i = 1; i <= n; ++ i)

        l[i] = rint(), y[i] = rint();

    g[0] = 1;

    for (register int i = 1; i <= k; ++ i)

        for (register int j = 1; j <= n; ++ j) if (i - l[j] >= 0)

            g[i] = (g[i] + g[i - l[j]]) % mod;

    for (register int i = 1; i <= k; ++ i)

        for (register int j = 1; j <= n; ++ j) if (i - l[j] >= 0)

            f[i][y[j]] = (f[i][y[j]] + g[i - l[j]]) % mod;

    char op[3];

    for (register int i = 1; i <= m; ++ i) {

        rstr(op);

        cnt[op[0] - 'A'] ++;

    }

    LL ans = 1;

    for (register int i = 0; i < 26; ++ i) if (cnt[i]) {

        LL res = 0;

        for (register int j = 1; j <= n; ++ j) if (f[k][j]) {

            res = (res + qpow(f[k][j], cnt[i]) % mod) % mod;

        }

        ans = ans * res % mod;

    }

    cout << ans << endl;

    return 0;

}