网站开发产品经理招聘,网站建设学习学校,泰州住房和城乡建设厅网站首页,wordpress+机械模板[NOIP2002 普及组] 产生数
题目描述
给出一个整数 n n n 和 k k k 个变换规则。
规则#xff1a;
一位数可变换成另一个一位数。规则的右部不能为零。
例如#xff1a; n 234 , k 2 n234,k2 n234,k2。有以下两个规则#xff1a; 2 ⟶ 5 2\longrightarrow 5 2⟶5。 …[NOIP2002 普及组] 产生数
题目描述
给出一个整数 n n n 和 k k k 个变换规则。
规则
一位数可变换成另一个一位数。规则的右部不能为零。
例如 n 234 , k 2 n234,k2 n234,k2。有以下两个规则 2 ⟶ 5 2\longrightarrow 5 2⟶5。 3 ⟶ 6 3\longrightarrow 6 3⟶6。
上面的整数 234 234 234 经过变换后可能产生出的整数为包括原数: 234 234 234。 534 534 534。 264 264 264。 564 564 564。
共 4 4 4 种不同的产生数。
现在给出一个整数 n n n 和 k k k 个规则。求出经过任意次的变换 0 0 0 次或多次能产生出多少个不同整数。
仅要求输出个数。
输入格式
第一行两个整数 n , k n,k n,k含义如题面所示。
接下来 k k k 行每行两个整数 x i , y i x_i,y_i xi,yi表示每条规则。
输出格式
共一行输出能生成的数字个数。
样例 #1
样例输入 #1
234 2
2 5
3 6样例输出 #1
4提示
对于 100 % 100\% 100% 数据满足 n 1 0 30 n \lt 10^{30} n1030 k ≤ 15 k \le 15 k≤15。
【题目来源】
NOIP 2002 普及组第三题
#includebits/stdc.h
using namespace std;
int tag[10][10];
int d[10];
int p[1000];
int main(){string a;int n;while(cinan){int x,y;for(int i0;in;i){cinxy;tag[x][y]1;}for(int k1;k9;k)for(int i0;i9;i)for(int j0;j9;j)if(tag[i][k]tag[k][j]) tag[i][j]1;for(int i0;i10;i){tag[i][i]1;for(int j0;j10;j)if(tag[i][j])d[i];}int z0;p[0]1;for(int i0;a[i];i){z0;int xd[a[i]-0];for(int i0;i500;i){p[i](p[i]*xz);zp[i]/10;p[i]%10;}}int i500;while(p[i]0) i--;for(;i0;i--){coutp[i];}coutendl;}
}
