[USACO11FEB] Cowlphabet G
题意
有 \(P\) 种拼接方式，问由 \(U\) 个大写字母和 \(L\) 个小写字母合法组合的方案数。
输出方案数对 \(97654321\) 取模的值。
思路
动态规划，还没有人写逆推方法，刚好我做的逆推。
设 \(f[i][j][z]\) 表示一共有 \(i\) 个字母，其中 \(j\) 个为小写字母，最后一个字母为 \(z\) 的方案数。
那么 \(f[i][j][z]\) 的值为长度为 \(i-1\) 且最后一个字母能和 \(z\) 合法拼接的方案数之和。
设 \(la\) 为能在 \(z\) 前面和 \(z\) 合法组合的字母。
考虑 \(z\) 是大写还是小写：
- 若 \(z\) 是大写，那么应由所有 \(f[i-1][j][la]\) 转移过来。
- 否则应由所有 \(f[i-1][j-1][la]\) 转移过来。
最后枚举最后一位是什么字母累加统计答案即可。
代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod=97654321;
ll U, L, P;
ll f[502][251][54]; //f[i][j][z]表示一共有i个字母，其中有j个小写字母，最后一个字母为z的方案数
vector <int> can[54];
int get(char c) {
if(c>='a'&&c<='z') return c-'a'+1;
return c-'A'+27;
}
int main() {
cin >> U >> L >> P;
char c1, c2;
for(int i=1; i<=P; i++) {
cin >> c1 >> c2;
can[get(c2)].push_back(get(c1)); //因为是枚举上一位所以要反向统计
}
for(int i=1; i<=26; i++) f[1][1][i]=1;
for(int i=27; i<=52; i++) f[1][0][i]=1;
for(int i=2; i<=U+L; i++) {
for(int j=0; j<=L; j++) {
for(int z=1; z<=52; z++) {
for(int la:can[z]) {
if(z<=26&&j) f[i][j][z]=(f[i][j][z]+f[i-1][j-1][la])%mod;
else if(z>26) f[i][j][z]=(f[i][j][z]+f[i-1][j][la])%mod;
}
}
}
}
ll ans=0;
for(int i=1; i<=52; i++) ans=(ans+f[U+L][L][i])%mod;
cout << ans;
return 0;
}