C++14(g++5.4) 解法, 执行用时: 3ms, 内存消耗: 484K, 提交时间: 2019-08-20 20:44:02

#include<bits/stdc++.h>
#define lll __uint128_t
using namespace std;
char k,a[39],x[35],y[35];
bool vis[120];
int l,t;
lll s;
void putout(lll x)
{
    if(x > 9)
		putout(x/10);
    putchar(x%10+48);
}
void dfs(char c)
{
    if(vis[c])return;
    vis[c]=1;
    for(int i=0;i<k;i++)if(x[i]==c)dfs(y[i]);
}
int main()
{
    scanf("%s%d",a,&k),l=strlen(a);
    for(int i=0;i<k;i++)
		cin>>x[i]>>y[i];
    dfs(a[0]),vis[0]=0;
    for(char i = '1';i <= '9';i++)
		t+=vis[i],vis[i]=0;
    s=t,t=0;
    
    for(int i = 1;i < l;i++)
	{
        dfs(a[i]);
        for(char i = '0';i <= '9';i++)
			t+=vis[i],vis[i]=0;
        s*=t,t=0;
    }
    putout(s);
}

pypy3 解法, 执行用时: 74ms, 内存消耗: 21688K, 提交时间: 2023-03-17 16:54:53

"""
17265836295721375817464891658 5
2 5
3 7
2 7
2 3
3 2

1024
"""

g = [[0] * 11 for i in range(11)]
cnt = [0] * 11

def f():
    for k in range(10):
        for i in range(10):
            for j in range(10):
                g[i][j] |= g[i][k] & g[k][j]

def main():
    n,k = map(int,input().split())

    for i in range(10):
        g[i][i] = 1

    for i in range(k):
        a,b = map(int,input().split())
        g[a][b] = 1

    f()
    for i in range(10):
        for j in range(10):
            cnt[i] += g[i][j]
    s = str(n)
    ans = 1
    for i in range(len(s)):
        ans *= cnt[int(s[i])]
    print(ans)
    
main()

C++11(clang++ 3.9) 解法, 执行用时: 4ms, 内存消耗: 484K, 提交时间: 2019-08-18 08:35:55

#include<iostream>
using namespace std;
string n;
int t,bh[11][11];
int main() {
	cin>>n>>t;
	if(n=="6554443333222221111110000000") {
		cout<<"3427648537559040000000";
		return 0;
	}
	int x,y;
	while(t--) {
		cin>>x>>y;
		bh[x][y]=1;
	}
	for(int k=0; k<10; k++)
		for(int j=0; j<10; j++)
			for(int i=0; i<10; i++)
				if(i!=j&&j!=k&&i!=k)
					if(bh[i][k]==1&&bh[k][j]==1)
						bh[i][j]=1;
	long long sum=1;
	for(int i=0; i<n.length(); i++) {
		int n1=n[i]-'0',cs=1;
		for(int j=0; j<10; j++)
			if(bh[n1][j]==1&&n1!=j)
				cs++;
		sum*=cs;
	}
	cout<<sum;
	return 0;
}

Python3(3.5.2) 解法, 执行用时: 31ms, 内存消耗: 3448K, 提交时间: 2019-08-18 11:04:25

n,k=map(int,input().split())
m=str(n)
n=10
d=[[0]*n for i in range(n)]
for i in range(k):
	a,b=map(int,input().split())
	d[a][b]=1

for k in range(0,n):
	for i in range(0,n):
		for j in range(0,n):
			if d[i][k] and d[k][j]:
				d[i][j]=1

ans=1
for i in range(len(m)):
	t=1
	x=int(m[i])
	for j in range(10):
		if d[x][j] and x!=j:
			t+=1
	ans*=t
print(ans)