CF1907E

FiraCode · 2023-12-26 22:18:45 · 题解

思路：

我们考虑一个性质：当他们出现进位时就一定不可以。

因为当出现进位，那么他们的和对下一位的贡献要比进位增加的贡献大，所以最后他们每个数位的和一定大于 n 数位的和。

那么实际上每一位是独立的，考虑直接预处理出当数位和为 k(0\le k\le9) 时有序三元组的方案数。

最后每一位乘起来即可。

Code

#include <bits/stdc++.h>

using namespace std;

int T;
int n;
int sum = 9;
array<int, 3> a;
int res = 0;
int f[10];

int main() {
    scanf("%d", &T);
    for (int i = 0; i <= 9; ++i) {
        for (int j = 0; j <= 9; ++j)
            for (int k = 0; k <= 9; ++k)
                for (int p = 0; p <= 9; ++p) {
                    if (j + k + p == i) ++f[i];
                }
    }
    while (T--) {
        scanf("%d", &n);
        vector<int> a;
        while (n) {
            a.push_back(n % 10);
            n /= 10;
        }
        long long ans = 1;
        for (int i = 0; i < (int)a.size(); ++i) ans = 1ll * ans * f[a[i]];
        printf("%lld\n", ans);
    }
    return 0;
}