（ssl 1021 洛谷 1037）产生数#floyd#

本文主要是介绍（ssl 1021 洛谷 1037）产生数#floyd#，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

给出一个整数 $n$ 和 $k$ 个规则。
经过任意次的变换（0次或多次），能产生出多少个不同整数。仅要求输出个数。

---

分析

首先这道题明显的 最短路径（难道还用深搜）
根据乘法原理答案等于0~9的状态数乘积
n超过30位,根据分析最大答案也就10^30了。
所以数组只用开到三十（为了保险，开到一百）
so其实虽然我知道__int 128，但是毕竟学校题库编译错误，所以还是得用高精度。
然后关键就是这种情况
2 1
3 2
4 3
5 4
6 5
7 6
8 7
9 8
0 9
所以需要最短路径。

#include <cstdio>
#include <cctype>
using namespace std;
const int maxn=100;
char b[maxn+1]; int n,x,y,c[11],a[11];
bool g[11][11];
void times(int s){//高精度乘法int g=0,h=0;for (int i=maxn;i>=1;i--){h=s*b[i]+g;g=h/10;b[i]=h%10;}
}
void print(){//输出int j=1;while (j<maxn&&!b[j]) j++;for (int i=j;i<=maxn;i++) putchar(b[i]+48);
}
int main(){char u=getchar();while (isdigit(u)) a[u-48]++,u=getchar();scanf("%d",&n); b[maxn]=1;for (int i=1;i<=n;i++) scanf("%d%d",&x,&y),g[x][y]=1;for (int i=0;i<=9;i++) g[i][i]=1;//自己也是状态for (int k=0;k<=9;k++)for (int i=0;i<=9;i++)for (int j=0;j<=9;j++)g[i][j]=(g[i][j]||(g[i][k]&&g[k][j]));//判断是否连通的floydfor (int i=0;i<=9;i++)for (int j=0;j<=9;j++) c[i]+=g[i][j];//计算状态数for (int i=0;i<=9;i++)for (int j=1;j<=a[i];j++) times(c[i]);print(); return 0;
}

这篇关于（ssl 1021 洛谷 1037）产生数#floyd#的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---