29 lines
1.1 KiB
C++
29 lines
1.1 KiB
C++
// P1037 产生数。十个数字的自反传递闭包 + 十进制高精度乘法。
|
|
#include <bits/stdc++.h>
|
|
using namespace std;
|
|
string mulSmall(string s, int k) {
|
|
int carry = 0;
|
|
for (int i = (int)s.size()-1; i >= 0; --i) {
|
|
int t = (s[i]-'0')*k + carry;
|
|
s[i] = char('0'+t%10); carry = t/10;
|
|
}
|
|
while (carry) { s.insert(s.begin(), char('0'+carry%10)); carry /= 10; }
|
|
return s;
|
|
}
|
|
int main() {
|
|
ios::sync_with_stdio(false); cin.tie(nullptr);
|
|
string number; int k; if (!(cin >> number >> k)) return 0;
|
|
bool reach[10][10] = {};
|
|
for (int i = 0; i < 10; ++i) reach[i][i] = true;
|
|
for (int i = 0, a, b; i < k; ++i) { cin >> a >> b; reach[a][b] = true; }
|
|
for (int mid = 0; mid < 10; ++mid)
|
|
for (int i = 0; i < 10; ++i)
|
|
for (int j = 0; j < 10; ++j)
|
|
reach[i][j] |= reach[i][mid] && reach[mid][j];
|
|
int choices[10] = {};
|
|
for (int a = 0; a < 10; ++a) for (int b = 0; b < 10; ++b) choices[a] += reach[a][b];
|
|
string ans = "1";
|
|
for (char digit : number) ans = mulSmall(ans, choices[digit-'0']);
|
|
cout << ans << '\n';
|
|
}
|