1009 产生数
题目描述 Description
给出一个整数 n（n<10^30) 和 k 个变换规则（k<=15）。
规则：
一位数可变换成另一个一位数：
规则的右部不能为零。
例如：n=234。有规则（k＝2）：
2－> 5
3－> 6
上面的整数 234 经过变换后可能产生出的整数为（包括原数）:
234
534
264
564
共 4 种不同的产生数
问题：
给出一个整数 n 和 k 个规则。
求出：
经过任意次的变换（0次或多次），能产生出多少个不同整数。
仅要求输出个数。
输入描述 Input Description
键盘输人，格式为：
n k
x1 y1
x2 y2
... ...
xn yn
输出描述 Output Description
屏幕输出，格式为：
一个整数（满足条件的个数）
样例输入 Sample Input
234 2
2 5
3 6
样例输出 Sample Output
4
个人解法：
显然就是一个一眼看得出来的构造题。
这是一个十进制数，那么只有0到9一共10个符号。现在就是这些符号之间可以怎么转换。
拿样例说事。
对于一个234，我们有3个符号：“2”，“3”，“4”。“2”可以换成“5”，“3”可以换成“6”。
那么事实上就是“234”这个数的第一位有2种取法：“2”和“5”，第二位有2种取法：“3”和“6”。第三位有一种取法：“4”。
答案就是2*2*1种取法，也就是4。
所以最后的关键就是如何找到当前的符号可以转换为多少种符号。如果符号k可以转换为x种，那么原来的数字中是符号k的那一位就可以转换成(x+1)种数字。最后是每一位上的数字可以转换的个数之积。
那么我们怎么找一个符号可以转换为多少个符号呢？
如果符号k可以转换为符号g，那么从k到g建一条边。（看到楼下很多题解都是这样）接下来BFS或者DFS。跑Floyed的人简直就是在嘲笑数据范围，但是好写——所以也是一个不错的选择。
（真搞不懂为什么这是一个10进制的，1000进制的都可以随便过了）。
对于每一个符号都BFS一遍，复杂度是O(M^2)的。M表示这个数是M进制数。
代码如下：
type
inf=record
x,next:longint;
end;
var
Arr,Cando:array[1..30] of longint;//Arr记录数字n的每一位上的数。Cando[i]表示i这一位的符号可以转换为多少个符号。
Changetime:array[0..9] of longint;//Changetime[i]记录的是第i个符号可以转换为多少个符号（不包括自己）
arrmap:array[0..9] of longint;
arre:array[1..15] of inf;//arrmap与arre存图
vis:array[0..9] of boolean;//BFS时的判重数组
an:string;
k,code,i,s,t,n,top:longint;
ans:int64;//答案要一个int64（longlong）
procedure ins(f,s:longint);//插入一条边
begin
inc(top);
arre[top].x:=s;
arre[top].next:=arrmap[f];
arrmap[f]:=top;
end;
procedure DFS(i,x:longint);//我似乎用的是DFS——反正不会炸空间就是了
var
v:longint;
begin
v:=arrmap[i];
while v<>0 do
begin
if not vis[arre[v].x] then
begin
inc(Changetime[x]);//如果找到了一个没有遍历过的，那么x就又多了一个可以转换到的。
vis[arre[v].x]:=true;
DFS(arre[v].x,x);
end;
v:=arre[v].next;
end;
end;
begin
readln(an);
n:=pos(' ',an);
val(copy(an,n+1,length(an)-n),k,code);
delete(an,n,length(an)-n+1);
n:=length(an);
for i:=1 to n do
val(an[i],Arr[i],code);//读入并记录每一位上的数字
for i:=1 to k do
begin
readln(s,t);
if s<>t then ins(s,t);//建边
end;
for i:=0 to 9 do//对于每一个符号都DFS一遍。找到当前这个符号可以转换为多少个符号。
begin
fillchar(vis,sizeof(vis),false);
vis[i]:=true;
DFS(i,i);
end;
for i:=1 to n do
inc(Cando[i],Changetime[Arr[i]]+1);//注意自己也可以转换为自己，而在BFS（DFS）中我们没有统计自己，所以这里+1。
ans:=1;
for i:=1 to n do
ans:=ans*int64(Cando[i]);//计算答案
writeln(ans);//输出
end.
这是可以O(M^2)过的。
所以这个算法可以解决1000进制的数。
但是如果对于一个10^6进制的数（做普及组的题目如果不多想一下优化可能就没什么意思了）？
那么我们就应该用一个O(n)的算法来解决每一个符号可以转换的其他字符的个数。
在实际模拟中我们发现如果在BFS(x)的时候经过了一个点y，那么y的答案似乎是可以由x得来的。
冥冥之中（这个词不太好）感觉路径上的点可以转换为的符号的个数是有关系的。
于是自然想到了一张拓扑图。
如果是一个拓扑图，那么毫无争议
Changetime[x]=sigma(Changetime[y])+1，其中x到y有边，且此时的Changetime[x]表示x可以转换为的符号数量（包括自己）。
那么对于一张任意图，我们发现互为强连通分量的点是可以相互转换的。
所以如果一个强连通分量包括有r个点，而将这个强连通分量视为一个符号后可以转换为e个符号（包括自己）。那么这个强连通分量里面的任何一个符号的都可以转换为r+e-1个符号（包括自己）。
所以思路就很清晰了。Tarjan一趟找到强连通分量，之后建一张拓扑图。对于这个拓扑图再拓扑排序一趟。得到所有缩点的Changetime之后再更新原点的Changetime（或者都不用更新了，直接O(1)调用）。
不过，如果x到y有一条边，那么就要用y的Changetime去更新x的。所以在Tarjan之后建图要反着建边，便于之后的拓扑排序。
所以这是一个O(M)的算法，也就是可以解决10^6进制数。
代码如下：
type
inf=record
x,next:longint;
end;
var
Arr,Cando:array[0..31] of longint;//Arr与Cando意义不变
Changetime,Dfn,Low,Nar,Stk,Size:array[0..10] of longint;//Changetime[x]表示x可以转换为多少个字符（包括x在内）。Dfn、Low、Stk在Tarjan中的意义就不必解释了，Nar[x]记录x对应的虚点编号。Size[x]记录x虚点由多少个实点组成
Darrmap,arrmap:array[0..10] of longint;
Darre,arre:array[1..16] of inf;//建图使用的邻接链表。
vis,Flag:array[0..10] of boolean;
an:string;
k,code,i,s,t,n,top,ant,cnt:longint;
ans:int64;
function min(a,b:longint):longint;//取最小值
begin
if a<b then exit(a);
exit(b);
end;
procedure ins(f,s:longint);//插入一条边
begin
inc(top);
arre[top].x:=s;
arre[top].next:=arrmap[f];
arrmap[f]:=top;
end;
procedure Tarjan(x:longint);//求虚点
var
v:longint;
begin
inc(cnt);
Dfn[x]:=cnt;
Low[x]:=cnt;
inc(top);
Stk[top]:=x;
Flag[x]:=true;
vis[x]:=true;
v:=arrmap[x];
while v<>0 do
begin
if not vis[arre[v].x] then
begin
Tarjan(arre[v].x);
Low[x]:=min(Low[x],Low[arre[v].x]);
end
else if Flag[arre[v].x] then Low[x]:=min(Low[x],Low[arre[v].x]);
v:=Arre[v].next;
end;
if Dfn[x]=Low[x] then
begin
inc(ant);
while Stk[top]<>x do
begin
inc(Size[ant]);
Nar[Stk[top]]:=ant;
dec(top);
end;
inc(Size[ant]);
Nar[Stk[top]]:=ant;//注意更新当前虚点是由多少个实点组成的
dec(top);
end;
end;
procedure Build;//反着建一张图
var
vi,v:longint;
begin
fillchar(Arre,sizeof(Arre),0);//图同样还是在Arre与Arrmap里面
fillchar(Arrmap,sizeof(Arrmap),0);
fillchar(Low,sizeof(Low),0);//这个时候Low记录的是点的入度
for vi:=0 to 9 do
begin
v:=Darrmap[vi];
while v<>0 do
begin
if Nar[Darre[v].x]<>Nar[vi] then
begin
ins(Nar[Darre[v].x],Nar[vi]);
inc(Low[Nar[vi]]);
end;
v:=Darre[v].next;
end;
end;
end;
procedure Topo;//拓扑排序
var
vi,v,x:longint;
begin
fillchar(Stk,sizeof(Stk),0);//Stk是拓扑排序的栈（显然队列也可以）
fillchar(Dfn,sizeof(Dfn),0);//Dfn[x]记录的是x虚点的Changetime
top:=0;
for vi:=1 to ant do
if Low[vi]=0 then
begin
inc(top);
Stk[top]:=vi;
Dfn[Stk[top]]:=1;
end;
while top<>0 do
begin
x:=Stk[top];
Stk[top]:=0;
dec(top);
v:=Arrmap[x];
while v<>0 do
begin
inc(Dfn[Arre[v].x],Dfn[x]);//用y去更新x的操作。本来是由x指向y的单向边，但是由于之后用虚点建图时边是反向的，就可以直接更新了。
dec(Low[Arre[v].x]);
if Low[Arre[v].x]=0 then
begin
inc(top);
Stk[top]:=Arre[v].x;
inc(Dfn[Stk[top]]);//由于此时的定义是包括自己的，所以要+1。
end;
v:=Arre[v].next;
end;
end;
end;
begin
readln(an);
n:=pos(' ',an);
val(copy(an,n+1,length(an)-n),k,code);
delete(an,n,length(an)-n+1);
n:=length(an);
for i:=1 to n do
val(an[i],Arr[i],code);//一样的读入
for i:=1 to k do
begin
readln(s,t);
if s<>t then ins(s,t);//建边
end;
top:=0;
for i:=0 to 9 do
if not vis[i] then Tarjan(i);//找强连通分量
Darrmap:=Arrmap;
Darre:=Arre;
Build;//重新建图
Topo;//拓扑排序
for i:=0 to 9 do
inc(Changetime[i],Dfn[Nar[i]]+Size[Nar[i]]-1);//统计每一个符号可以变为的符号个数（包括自己）
for i:=1 to n do
inc(Cando[i],Changetime[Arr[i]]);//计算每一位上的符号可以转换为多少个符号（包括自己）
ans:=1;
for i:=1 to n do
ans:=ans*int64(Cando[i]);//计算答案
writeln(ans);//输出
end.
话说事实上数据范围一大，普及组就可以摇身一变提高组了。所以也不是说普及组的没有思维难度。