【圖論】【RQNOJ】産生數

題目描述

　給出一個整數 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

輸出格式

　 螢幕輸出，格式為：

　　一個整數（滿足條件的個數）：

樣例輸入

樣例輸出

三維狀态圖像

計算有向圖的傳遞閉包。

然後乘法原理，hp，AC。

#include<stdio.h>

#include<string.h>

bool can[10][10];

int rules[10];

int ans[1000000];

int len,n,k;

char s[100];

int main()

{

scanf("%s",s);

scanf("%d",&k);

for (int i=1;i<=k;++i)

{

int a,b;

scanf("%d%d",&a,&b);

can[a][b]=true;

}

for (int i=0;i<10;++i) can[i][i]=true;

for (int k=0;k<10;++k)

for (int i=0;i<10;++i)

for (int j=0;j<10;++j)

can[i][j]=can[i][j]||(can[i][k]&&can[k][j]);

for (int i=0;i<10;++i)

for (int j=0;j<10;++j)

if (can[i][j]) ++rules[i];

ans[1]=len=1;

for (int i=0;i<strlen(s);++i)

{

int x=rules[s[i]-'0'];

for (int j=1;j<=len;++j) ans[j]*=x;

for (int j=1;j<=len;++j)

{

ans[j+1]+=ans[j]/10;

ans[j]%=10;

}

while (ans[len])

{

ans[len+1]+=ans[len]/10;

ans[len]%=10;

++len;

}

}

for (int i=len-1;i>0;--i) printf("%d",ans[i]);

return 0;

}