P1037 产生数

首先，这个题想都不想，肯定要高精。。。

于是直接粘贴板子。。。

本蒟蒻的$Flag$：

然后看一个栗子：

假如现在有两种变换：$1->2,2->3$。

那么无形中我们就有了一种变换：$1->3$。

这个变换也是可以达成的，所以要计算到答案里去。

但是这玩意怎么算呢？？？

暴力$DFS$？铁定$TLE$。。。

我们可以直接$Floyd$！

具体见代码。

然后问题就变成了：已知某个数字能变换到几种数字，求总的变换方案数。

这玩意直接利用乘法原理：

对于$N$的每一位数字，将这个数字能变换到的数字的个数乘进答案中。

很明显这个过程要用到高精度。

然后就没有了。。。

附代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define MAXN 11
#define MAXM 1010
using namespace std;
int m;
int num[MAXN];
bool map[MAXN][MAXN];
struct Number{
    int len,val[MAXM];
    void read(){
        len=0;
        int date=0;char c=0;
        while(c<'0'||c>'9')c=getchar();
        while(c>='0'&&c<='9'){val[++len]=c-'0';c=getchar();}
        for(int i=1;i<=len/2;i++)swap(val[i],val[len-i+1]);
    }
    void print(){
        for(int i=len;i>=1;i--)putchar(val[i]+'0');
        putchar('\n');
    }
    void clean(){
        len=0;
        memset(val,0,sizeof(val));
    }
    void new_number(int k){
        clean();
        while(k){
            val[++len]=k%10;
            k/=10;
        }
    }
    friend Number operator *(const Number &p,const Number &q){
        Number s;
        s.clean();
        s.len=p.len+q.len+2;
        for(int i=1;i<=q.len;i++){
            int c=0;
            for(int j=1;j<=p.len;j++){
                s.val[i+j-1]+=q.val[i]*p.val[j]+c;
                c=s.val[i+j-1]/10;
                s.val[i+j-1]%=10;
            }
            s.val[i+p.len]+=c;
        }
        while(!s.val[s.len])s.len--;
        return s;
    }
}n,ans;
inline int read(){
    int date=0,w=1;char c=0;
    while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
    while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
    return date*w;
}
void floyd(){
    for(int k=0;k<=9;k++)
    for(int i=0;i<=9;i++)
    for(int j=0;j<=9;j++)
    map[i][j]|=(map[i][k]&map[k][j]);
}
void work(){
    Number x;
    ans.new_number(1);
    for(int i=1;i<=n.len;i++){
        x.new_number(num[n.val[i]]);
        ans=ans*x;
    }
    ans.print();
}
void init(){
    int x,y;
    n.read();m=read();
    for(int i=1;i<=m;i++){
        x=read();y=read();
        map[x][y]=true;
    }
    floyd();
    for(int i=0;i<=9;i++){
        map[i][i]=true;
        for(int j=0;j<=9;j++)if(map[i][j])num[i]++;
    }
}
int main(){
    init();
    work();
    return 0;
}