Cow Poetry (USACO Gold 2019 January)

这是个相对直观的无限背包DP + 乘法原理的题。

首先每行诗之间是独立的，所以根据乘法原理，总的方案数就等于每一行的方案数乘起来。问题转化为求长度为 $K$ ，且以韵部(rhyme)为 $j$ 的单词结束的一行诗的可能方案数。

不考虑结尾单词的话，比较明显计算这个方案数是一个无限背包DP的问题，就是定义 $\text{dp}[i]$ : $i$ 个音节的行的方案数。状态转移是清楚的。

因为只有最后一个单词有韵部要求，我们可以直接用上面的DP定义来求最终结果，也就是枚举所有属于这个韵部的单词 $w$ ，以这个单词结尾的方案数就是 $\text{dp}[K-\text{len}(w)]$ ，全部加起来就行了。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int n,m,K;
int dp[5005];   // number of combinations with exactly i syllables
                // infinite knapsack
struct W {
    int len;    // syllables of words
    int rhy;    // rhymes of words
};
W wd[5005];
int cnt[26];                // 26 rhymes
vector<int> cls[5005];      // words in rhyme classes
const int MOD = 1e9+7;
 
int modpow(int x, int y) {  // mod power
    if (y == 0) return 1;
    if (y == 1) return x;
    int u = modpow(x, y/2);
    int r = (ll)u*u%MOD;
    if (y % 2)
        r = (ll)r*x%MOD;
    return r;
}
 
int main() {
    scanf("%d %d %d", &n, &m, &K);
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &wd[i].len, &wd[i].rhy);
        cls[wd[i].rhy].push_back(i);
    }
    for (int i = 0; i < m; i++) {
        char s[10];
        scanf("%s", s);
        cnt[s[0]-'A']++;
    }
    dp[0] = 1;
    for (int i = 1; i <= K; i++)
        for (int j = 0; j < n; j++)
            if (i - wd[j].len >= 0)
                dp[i] = ((ll)dp[i] + dp[i-wd[j].len]) % MOD;
    int ans = 1;
    for (int i = 0; i < 26; i++) {
        int sum = 0;
        int c = cnt[i];         // lines in this group
        if (c == 0) continue;
        for (int j = 1; j <= n; j++) {  // result for rhyme class j
            int sum2 = 0;
            if (cls[j].size() == 0) continue;
            for (int w: cls[j]) {
                if (K-wd[w].len >= 0)
                    sum2 = ((ll)sum2 + dp[K-wd[w].len]) % MOD;
            }
            sum = ((ll)sum + modpow(sum2, c)) % MOD;
        }
        ans = (ll)ans * sum % MOD;
    }
    printf("%d", ans);
    return 0;
}