题目链接

https://www.dotcpp.com/oj/problem1492.html

题目大意

每个数（0 ~ 9）可以变换成其他的数（除本身外0 ~ 9）。
给定一个数，问这个数可以有多少种形式（包含原形）

解题思路

思路很简单，把这个数中每一位数可以变换的种数相乘，得到答案。
难点1：如何统计每个数可以变换的种数（含自己）？
难点2：最终答案的最大可能为：每一位数都有10种变换（含自己），答案是10^30，比longlong大，怎么表达这个数？
难点2解决：这么大的数，自然相当高精度乘法（高精度*低精度），解决！
难点1解决：给出的变换规则，相当于一个图，关系是有向边，a能变成b，意味着a到b存在一条有向边。存下所有边之后，我们可以dfs遍历并统计其能到达的所有点的个数，用数组记录下来。进行高精度乘法的时候使用。

高精度*低精度板子

如果不会高精度乘法，建议先看看通过数组实现高精度的板子，再看容器实现的板子

//函数部分
vector<int> mul(vector<int> a,int b){
    vector<int> c;
    int t=0;
    for(int i=0;i<a.size();i++){
        t=a[i]*b+t;
        c.push_back(t%10);
        t/=10;
    }
    while(t){//把剩余没保存在vector中的数，保存进去
        c.push_back(t%10);
        t/=10;
    }
    return c;
}
//主函数部分
vector<int> res;
res.push_back(1);
for(int i=1;i<=len;i++){
        res=mul(res,k);//表示k与res相乘
}

大佬代码

#include<bits/stdc++.h>
using namespace std;
int len,cnt,k,p,q;
int vis[10],num[10],a[50];
vector<int> v[10];
vector<int> res;
char s[50];

void dfs(int x){
    for(int i=0;i<v[x].size();i++){
        int next=v[x][i];
        if(vis[next]) continue;
        cnt++;
        vis[next]=1;
        dfs(next);
    }
    return ;
}
vector<int> mul(vector<int> a,int b){
    vector<int> c;
    int t=0;
    for(int i=0;i<a.size();i++){
        t=t+a[i]*b;
        c.push_back(t%10);
        t/=10;
    }
    while(t){
        c.push_back(t%10);
        t/=10;
    }
    return c;
}
int main(){
    cin>>s+1>>k;
        //存边
    for(int i=1;i<=k;i++){
        cin>>p>>q;
        v[p].push_back(q);
    }
    //逆置字符串
    len=strlen(s+1);
    for(int i=1;i<=len;i++)
        a[len-i+1]=s[i]-'0';
    //dfs
    for(int i=0;i<=9;i++){
        cnt=1;//初始化的时候直接加上自己这个点
        memset(vis,0,sizeof vis);
        vis[i]=1;//勿忘，但其实好像对本题的数据没影响
        dfs(i);
        num[i]=cnt;//num用于存数字i可变种数
    }
    //*
    res.push_back(1);//勿忘
    for(int i=1;i<=len;i++){
        res=mul(res,num[a[i]]);
    }
    //输出 
    for(int i=res.size()-1;i>=0;i--)
        cout<<res[i];
    cout<<endl;
    return 0;
}

我的代码

和大佬的差别在于dfs。我的比较混乱，多用了个set容器。其他部分一样。
所以，可以忽略我的代码

#include<bits/stdc++.h>
using namespace std;
const int N=50;
int fa;
int vis[10];
vector<int> a[10];
int cnt[N];
set<int> num[10];
char n[N];
int c[N];
vector<int> mul(vector<int> a,int b){
    vector<int> c;
    int t=0;
    for(int i=0;i<a.size();i++){
        t=a[i]*b+t;
        c.push_back(t%10);
        t/=10;
    }
    while(t){
        c.push_back(t%10);
        t/=10;
    }
    return c;
}
void dfs(int x){
    for(int i=0;i<a[x].size();i++){
        int tmp=a[x][i];
        if(tmp==fa || vis[tmp]) continue;
        num[fa].insert(tmp);
        vis[tmp]=1;
        dfs(tmp);
    }
    return ;
}
int main(){
    int k,p,q;
    cin>>n+1>>k;
    //存边 
    for(int i=1;i<=k;i++){
        cin>>p>>q;
        a[p].push_back(q);
    }
    //找到每个数能变成的全部数    
    for(int i=0;i<=9;i++){
        fa=i;
        memset(vis,0,sizeof vis);
        vis[i]=1; 
        dfs(i);
    }
    //计算每个数能变成其他数的个数        
    for(int i=0;i<=9;i++)
        cnt[i]=num[i].size();
    //逆置字符串 
    int len=strlen(n+1);
    for(int i=1;i<=len;i++)    
        c[len-i+1]=n[i]-'0';
    //高精度乘法 
    vector<int> res;
    res.push_back(1);
    for(int i=1;i<=len;i++){
        res=mul(res,cnt[c[i]]+1);
    }
    //输出 
    for(int i=res.size()-1;i>=0;i--)
        cout<<res[i];
    cout<<endl;

    return 0;
} 

总结

这是我们昨天蓝桥训练的一道题，昨天还不会，今天看完高精度，思路都清晰了，直接AC，神了！