题解：P3012 [USACO11FEB] Cowlphabet G

Welcome to Anins's Blogs / 2024-11-17 / 原文

[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;
}