背景
给出一个整数 n(n<10^30) 和 k 个变换规则(k<=15)。
规则:
一位数可变换成另一个一位数:
规则的右部不能为零。
例如:n=234。有规则(k=2):
2-> 5
3-> 6
上面的整数 234 经过变换后可能产生出的整数为(包括原数):
234
534
264
564
共 4 种不同的产生数
描述
给出一个整数 n 和 k 个规则。
求出:
经过任意次的变换(0次或多次),能产生出多少个不同整数。
仅要求输出个数。
格式
输入格式
n k
x1 y1
x2 y2
... ...
xn yn
输出格式
一个整数(满足条件的个数):
限制
每个测试点1s
来源
noip2002普及组第三题
----------------
一个数可以变换多次,floyd求传递闭包(初始化d[i][i]=1),乘法原理更新答案
要用高精度,注意输出
//
// main.cpp
// noip2002产生数
//
// Created by Candy on 9/10/16.
// Copyright © 2016 Candy. All rights reserved.
// #include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
typedef unsigned long long ll;
const int N=,B=1e4;
inline int read(){
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
} int k,x,y,d[N][N],f[N];
char s[N];
void floyd(){
for(int i=;i<=;i++) d[i][i]=;
for(int k=;k<=;k++)
for(int i=;i<=;i++)
for(int j=;j<=;j++)
d[i][j]=d[i][j]||(d[i][k]&&d[k][j]);
for(int i=;i<=;i++)
for(int j=;j<=;j++) if(d[i][j]) f[i]++;
}
struct big{
int d[],size;
big(){size=;}
} ans;
void chengInt(big &a,int k){
int g=,i;
for(i=;i<=a.size;i++){
int tmp=a.d[i]*k;
a.d[i]=(tmp+g)%B;
g=(tmp+g)/B;
}
while(g){
a.d[i++]=g%B; a.size++;
g/=B;
}
}
int main(int argc, const char * argv[]) {
scanf("%s%d",s,&k);
for(int i=;i<=k;i++) scanf("%d%d",&x,&y),d[x][y]=;
floyd();
ans.d[]=;
int len=strlen(s);
for(int i=;i<len;i++){
int a=s[i]-'';
chengInt(ans,f[a]);
//printf("f %d %d\n",a,f[a]);
}
for(int i=ans.size;i>=;i--){
if(i!=ans.size){
if(ans.d[i]<) cout<<"";
else if(ans.d[i]<) cout<<"";
else if(ans.d[i]<) cout<<"";
}
cout<<ans.d[i];
}
return ;
}