自动搬运

查看原文

来自洛谷，原作者为

	tXX_F 你家BestMonkey叫Banksy吗？

搬运于2025-08-24 21:44:23，当前版本为作者最后更新于2024-08-16 13:12:10，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P3012 [USACO11FEB] Cowlphabet G

题解

可以设 $f_{i,j,k}$ 表示总共有 $i$ 个字符，大写字母有 $j$ 个，末尾字母的为 $k$ 的字串的方案数。

可推出转移式子为：

• 若下一个字母为小写： $f_{i+1,j,k}\gets f_{i+1,j,k}+f_{i,j,w}$

• 若下一个字母为大写： $f_{i+1,j+1,k}\gets f_{i+1,j+1,k}+f_{i,j,w}$

为了实际处理方便，可以将大小写字母转换为数字，即 $a\sim z$ 用 $1\sim 26$ 表示，$A\sim Z$ 用 $27\sim 52$ 表示。

最终答案就为：$\sum_{i=1}^{52}f_{U+L,U,i}$。

Code

#include<bits/stdc++.h>
using namespace std;
const int Mod=97654321,Maxn=250+5;;
int U,L,P;
vector<int>Vec_S[57];
int F[Maxn<<1][Maxn][57];
int Answer;
inline int Get(char c){
	return c>='a'&&c<='z'?c-'a'+1:c-'A'+1+26;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>U>>L>>P;
	char s_1,s_2;
	for(register int i=1;i<=P;++i){
		cin>>s_1>>s_2;
		Vec_S[Get(s_1)].push_back(Get(s_2));
	}
	for(register int i=1;i<=26;++i){
		F[1][0][i]=1;
		F[1][1][i+26]=1;
	}
	int len;
	for(register int i=1;i<=U+L;++i)
		for(register int j=0;j<=U;++j)
			for(register int k=1;k<=52;++k){
				len=Vec_S[k].size();
				for(register int p=0;p<len;++p){
					if(Vec_S[k][p]<=26)
						(F[i+1][j][Vec_S[k][p]]+=F[i][j][k])%=Mod;
					else
						(F[i+1][j+1][Vec_S[k][p]]+=F[i][j][k])%=Mod;
				}
			}
	for(register int i=1;i<=52;++i)
		(Answer+=F[U+L][U][i])%=Mod;
	cout<<Answer<<endl;
	return 0;
}