2479: 产生数
内存限制:256 MB
时间限制:1.000 S
评测方式:文本比较
命题人:
提交:0
解决:0
题目描述
给出一个整数n(n≤2000)和k个变换规则(k≤15)。规则:
① 1个数字可以变换成另1个数字;
② 规则中,右边的数字不能为零。
例如:n=234,k=2规则为2 → 5,3 → 6
上面的整数234经过变换后可能产生出的整数为(包括原数)234,534,264,564共4种不同的产生数。
求经过任意次的变换(0次或多次),能产生出多少个不同的整数。仅要求输出不同整数个数。
① 1个数字可以变换成另1个数字;
② 规则中,右边的数字不能为零。
例如:n=234,k=2规则为2 → 5,3 → 6
上面的整数234经过变换后可能产生出的整数为(包括原数)234,534,264,564共4种不同的产生数。
求经过任意次的变换(0次或多次),能产生出多少个不同的整数。仅要求输出不同整数个数。
输入
n
k
x1 x2 … xn
y1 y2 … yn
k
x1 x2 … xn
y1 y2 … yn
输出
格式为一个整数(满足条件的整数个数)。
样例输入 复制
234
2
2 5
3 6
样例输出 复制
4
提示
算法分析:可以看成是一张10*10的图,根据变化规则,用用Floyd算法求点到点之间的连通关系,横纵座标值相同表示数值没有变化,计入初始变化方案数。输入的原数从第一位开始,依次按变化方案数进行累乘,就是最后结果。