Luogu P1037 产生数

题目传送门
Floyd + 乘法原理
只需要将每个数字能够变换的次数累乘即可。
这道题需要用到 Floyd 计算每个数字最多能够变换的次数（能够连续变换）

数字只有十个，邻接矩阵就能存的下，使用 tran[i][i] 数组表示i,j两个数之间是否可以变换。

void floyd() {
    for (int k = 0; k <= 9; k++)
        for (int i = 0; i <= 9; i++)
            for (int j = 0; j <= 9; j++)
                if ((tran[i][k] && tran[k][j]) || (i == j)) //注意自己也要计数
                    tran[i][j] = true;
}

此外结果范围会爆 long long，需要手写高精乘（从网上抄的板子)。

string mul(string x, int b) {
    string result="";
    int a[1000], c[1000], l , i, t, p = 0;
    memset(a, 0, sizeof(a));
    memset(c, 0, sizeof(c));
    l = x.length();
    for (i = l - 1; i >= 0; i--) a[l-i-1] = to_int(x[i]);
    for (i = 0; i < l; i++) {
        t = a[i] * b + c[i];
        p = 0;
        if (t >= 10) p = t / 10, t %= 10;
        c[i] += t - c[i];
        c[i + 1] += p;
    }
    if (p) l++;
    for (i = l - 1; i >= 0; i--) result += to_char(c[i]);
    return result;
}

完整版代码

#include <bits/stdc++.h>
using namespace std;
string n;
string ans = "1";
int k, var[12];
bool tran[32][32];
int to_int(char c) {
    return c - '0';
}
char to_char(int n) {
    return n + '0';
}
void floyd() {
    for (int k = 0; k <= 9; k++)
        for (int i = 0; i <= 9; i++)
            for (int j = 0; j <= 9; j++)
                if ((tran[i][k] && tran[k][j]) || (i == j))
                    tran[i][j] = true;
}
void stat() {
    memset(var, 0, sizeof(var));
    for (int i = 0; i <= 9; i++) {
        for (int j = 0; j <= 9; j++)
            if (tran[i][j]) var[i]++;
    }
}
string mul(string x, int b) {
    string result="";
    int a[1000], c[1000], l , i, t, p = 0;
    memset(a, 0, sizeof(a));
    memset(c, 0, sizeof(c));
    l = x.length();
    for (i = l - 1; i >= 0; i--) a[l-i-1] = to_int(x[i]);
    for (i = 0; i < l; i++) {
        t = a[i] * b + c[i];
        p = 0;
        if (t >= 10) p = t / 10, t %= 10;
        c[i] += t - c[i];
        c[i + 1] += p;
    }
    if (p) l++;
    for (i = l - 1; i >= 0; i--) result += to_char(c[i]);
    return result;
}
int main() {
    cin >> n >> k;
    for (int i = 1, n1, n2; i <= k; i++) {
        cin >> n1 >> n2;
        tran[n1][n2] = true;
    }
    floyd();
    stat();
    for (unsigned int i = 0; i < n.length(); i++)
        ans = mul(ans, var[to_int(n[i])]);
    cout << ans;
    return 0;
}