做完发现居然没人用map搞映射
特意来补充一发
很容易看出这是一道搜索题
考虑搜索方案，如果按字符串转移，必须存储每种状态，空间复杂度明显会爆炸
观察到每一位之间是互不影响的
考虑使用乘法原理
搜索出每一位的情况总数，求它们的连乘积即为答案
时间复杂度O(n2^k)
可以看出答案最大可以达到三十的十次方，会爆掉long long，所以需要写高精
具体处理可以选择STL（懒得自己写）
对于映射，这是map的专长
如果一个数能够映射到多个数呢？
用map的时候从char映射到vector<char>即可
代码：
#include<iostream>
#include<cstdio>
#include<map>
#include<vector>
#include<cstring>
using namespace std;
map<char,vector<char> >mp;
string st;
int k,l,c[],mul[];
void dfs(char th)
{
c[th-'']=;
int sz=mp[th].size();
for(int i=;i<sz;i++)
if(!c[mp[th][i]-''])
dfs(mp[th][i]);
}
signed main()
{
cin>>st>>k;
l=st.length();
for(int i=;i<=k;i++)
{
char x,y;
cin>>x>>y;
mp[x].push_back(y);
}
mul[]=;
for(int i=;i<l;i++)
{
memset(c,,sizeof(c));
dfs(st[i]);
int sum=;
for(int i=;i<=;i++)
sum+=c[i];
int x=;
for(int i=;i<;i++)
{
mul[i]=mul[i]*sum+x;
x=mul[i]/;
mul[i]%=;
}
}
int i=;
while(i>&&!mul[i])
i--;
for(;i>=;i--)
cout<<mul[i];
cout<<endl;
return ;
}