题解：P3012 [USACO11FEB] Cowlphabet G

tXX_F · 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;
}