ARC136C Circular Addition [高维前缀和]

Description

给定一个长度为 \(n\) 的正整数序列 \(A\)，求有多少对 \((i,j)\) 使得 \(A_i+A_j\) 不发生进位操作。
\(A_i<10^6\)。

Solution

显然对于每个 \(A_i\)，设 \(B_i=999999-A_i\)，那么 \(A_i\) 可以和 所有位上的数 都小于等于 \(B_i\) 对应位上的数 的数匹配，考虑用桶加前缀和统计（相当于是个 \(6\) 维前缀和）。
然后对于每位都 \(\le 4\) 的数，是会和它自己匹配的，所以要减 \(1\)。
最后答案 \(/2\) 即可。

Code

const int N = 1e6 + 5;

int n, a[N];
int p[6] = {1, 10, 100, 1000, 10000, 100000};
ll sum[N], ans;

void Solve(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        sum[a[i]]++;
    }
    for(int i = 0; i < 6; i++){
        for(int j = 0; j < 1000000; j++){
            if(j / p[i] % 10){
                sum[j] += sum[j - p[i]];
            }
        }
    }
    for(int i = 1; i <= n; i++){
        ans += sum[999999 - a[i]];
        bool flag = true;
        for(int j = 0; j < 6; j++){
            if(a[i] / p[j] % 10 >= 5){
                flag = false;
                break;
            }
        }
        if(flag) ans--;
    }
    cout << ans / 2 << endl;
}