[NOIP 2002 普及组] 产生数

知识点

传递闭包、乘法原理、高精度

解题思路

用10个数字构成有向图，Floyd求每位能经过任意次变换到达的数字。加入自身可达后，把原数每一位的可达数字数量相乘，使用高精度保存。

正确性说明

变换仅改变一个位置，位置之间互不影响。传递闭包恰表示允许任意次变换的可达关系；每个位置独立选一个可达数位，对应唯一最终数字串。右部不为0，因此非零首位不会变为0，数字串与整数没有前导零冲突。乘法原理给出总数。

易错点

必须包含0次变换；规则可能成环或重复；n可有30位，不能用机器整数读取。

复杂度

闭包O(10³)，高精度乘法次数等于输入位数；空间O(10²)加答案位数。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
struct Big{static const int B=10000;vector<int>d;Big(long long x=0){do{d.push_back(x%B);x/=B;}while(x);}void trim(){while(d.size()>1&&d.back()==0)d.pop_back();}bool operator<(const Big&o)const{if(d.size()!=o.d.size())return d.size()<o.d.size();for(int i=(int)d.size()-1;i>=0;i--)if(d[i]!=o.d[i])return d[i]<o.d[i];return false;}Big operator+(const Big&o)const{Big r;r.d.assign(max(d.size(),o.d.size())+1,0);int carry=0;for(int i=0;i<(int)r.d.size();i++){int v=carry+(i<(int)d.size()?d[i]:0)+(i<(int)o.d.size()?o.d[i]:0);r.d[i]=v%B;carry=v/B;}r.trim();return r;}Big operator*(const Big&o)const{vector<long long>v(d.size()+o.d.size()+1);for(int i=0;i<(int)d.size();i++)for(int j=0;j<(int)o.d.size();j++)v[i+j]+=1LL*d[i]*o.d[j];Big r;r.d.resize(v.size());for(int i=0;i<(int)v.size();i++){if(i+1<(int)v.size())v[i+1]+=v[i]/B;r.d[i]=v[i]%B;}r.trim();return r;}Big operator*(int x)const{return *this*Big(x);}Big operator/(int x)const{Big r=*this;long long rem=0;for(int i=(int)d.size()-1;i>=0;i--){long long v=rem*B+d[i];r.d[i]=v/x;rem=v%x;}r.trim();return r;}friend ostream&operator<<(ostream&os,const Big&a){os<<a.d.back();for(int i=(int)a.d.size()-2;i>=0;i--)os<<setw(4)<<setfill('0')<<a.d[i];return os;}};

int main(){string s;int k;cin>>s>>k;bool g[10][10]{};for(int i=0;i<10;i++)g[i][i]=true;while(k--){int x,y;cin>>x>>y;g[x][y]=true;}for(int t=0;t<10;t++)for(int i=0;i<10;i++)for(int j=0;j<10;j++)g[i][j]=g[i][j]||(g[i][t]&&g[t][j]);Big ans(1);for(char c:s){int cnt=0;for(int j=0;j<10;j++)cnt+=g[c-'0'][j];ans=ans*cnt;}cout<<ans<<'\n';}