题解：AT_arc136_d [ARC136D] Without Carry / ARIS0_0 - 18

小屹0_0 · 2026-04-26 20:18:12 · 题解

前言

别样的重题错题不可做题板子题大赛，鉴定该题属于板子题。

好整齐得到带代码。

思路

首先设每个数的个位十位百味千位万位十万位百万位分别是 x_{i,1} \sim x_{i,6}，然后条件等价于 \forall k \in [1, 6], x_{i,k} + x_{j,k} < 10。

核心肯定在于后面这个式子，我们大力转化，也就是说 x_{i,k} + x_{j,k} \leq 9 等价于 x_{i, k} \leq 9 - x_{j, k}。

然后你发现只需要 i 的所有位数都小于九减 j 的对应位。

这就是一个高维前缀和板子了，注意减去自己和自己然后除以二。

code

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pii pair<int, int>
#define piii pair<pii, int>
#define fi first
#define se second
const int N = 1e6 + 5;

namespace ARIS0_0{
    int n, a[N], pre[10][10][10][10][10][10];

    void init(){
    }
    void solve(){
        cin >> n;
        for (int i = 1; i <= n; i ++ ){
            cin >> a[i];
            pre[a[i] % 10][a[i] / 10 % 10][a[i] / 100 % 10][a[i] / 1000 % 10][a[i] / 10000 % 10][a[i] / 100000 % 10] ++;
        }
        for (int i = 1; i < 10; i ++ )
            for (int j = 0; j < 10; j ++ )
                for (int k = 0; k < 10; k ++ )
                    for (int l = 0; l < 10; l ++ )
                        for (int m = 0; m < 10; m ++ )
                            for (int n = 0; n < 10; n ++ )
                                pre[i][j][k][l][m][n] += pre[i - 1][j][k][l][m][n];
        for (int i = 0; i < 10; i ++ )
            for (int j = 1; j < 10; j ++ )
                for (int k = 0; k < 10; k ++ )
                    for (int l = 0; l < 10; l ++ )
                        for (int m = 0; m < 10; m ++ )
                            for (int n = 0; n < 10; n ++ )
                                pre[i][j][k][l][m][n] += pre[i][j - 1][k][l][m][n];
        for (int i = 0; i < 10; i ++ )
            for (int j = 0; j < 10; j ++ )
                for (int k = 1; k < 10; k ++ )
                    for (int l = 0; l < 10; l ++ )
                        for (int m = 0; m < 10; m ++ )
                            for (int n = 0; n < 10; n ++ )
                                pre[i][j][k][l][m][n] += pre[i][j][k - 1][l][m][n];
        for (int i = 0; i < 10; i ++ )
            for (int j = 0; j < 10; j ++ )
                for (int k = 0; k < 10; k ++ )
                    for (int l = 1; l < 10; l ++ )
                        for (int m = 0; m < 10; m ++ )
                            for (int n = 0; n < 10; n ++ )
                                pre[i][j][k][l][m][n] += pre[i][j][k][l - 1][m][n];
        for (int i = 0; i < 10; i ++ )
            for (int j = 0; j < 10; j ++ )
                for (int k = 0; k < 10; k ++ )
                    for (int l = 0; l < 10; l ++ )
                        for (int m = 1; m < 10; m ++ )
                            for (int n = 0; n < 10; n ++ )
                                pre[i][j][k][l][m][n] += pre[i][j][k][l][m - 1][n];
        for (int i = 0; i < 10; i ++ )
            for (int j = 0; j < 10; j ++ )
                for (int k = 0; k < 10; k ++ )
                    for (int l = 0; l < 10; l ++ )
                        for (int m = 0; m < 10; m ++ )
                            for (int n = 1; n < 10; n ++ )
                                pre[i][j][k][l][m][n] += pre[i][j][k][l][m][n - 1];
        int ans = 0;
        for (int i = 1; i <= n; i ++ )
            ans += pre[9 - a[i] % 10][9 - a[i] / 10 % 10][9 - a[i] / 100 % 10][9 - a[i] / 1000 % 10][9 - a[i] / 10000 % 10][9 - a[i] / 100000 % 10];
        for (int i = 1; i <= n; i ++ )
            if (max({a[i] % 10, a[i] / 10 % 10, a[i] / 100 % 10, a[i] / 1000 % 10, a[i] / 10000 % 10, a[i] / 100000 % 10}) <= 4)
                ans --;
        ans /= 2;
        cout << ans << "\n";
    }
    void single(){ init(), solve(); }
    void multi(){ init(); int T; cin >> T; while (T -- ) solve(); }
    void idmulti(){ init(); int id, T; cin >> id >> T; while (T -- ) solve(); }
};

signed main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    ARIS0_0::single();
}
// 你一定要回来看看啊。
// ARIS0_0 - 18