ARC158C All Pair Digit Sums 题解

题目链接

题意

设 \(f(x)\) 表示 \(x\) 的各位之和。例如 \(f(158)=1+5+8=14,f(2023)=2+0+2+3=7,f(1)=1\) 等。

给定一个正整数序列 \(A=(A_1,...,A_N)\)，求 \(\sum_{i=1}^N\sum_{j=1}^Nf(A_i+A_j)\)。

数据范围：\(1\le N\le 2\times 10^5,1\le A_i<10^{15}\)。

题解

这题思路非常自然，先计算出如果每次加法都没有进位，即若 \(f(A+B)=f(A)+f(B)\) 时的答案，为 \(2N\sum_{i=1}^Nf(A_i)\)。

考虑到每次加法进位都会使答案 \(-9\)，则只要统计有多少次进位即可。

从低到高地枚举每一位的进位，设当前为第 \(k\) 位，则在这一位进位的条件就是 \(A_i\bmod 10^{k+1}+A_j\bmod 10^{k+1}\ge 10^{k+1}\)。

那么取 \(x_i=A_i\bmod 10^{k+1}\)，对 \(x_i\) 进行排序，然后用二分或者 two pointers 即可。

时间复杂度为 \(O(KN\log N)\) 或 \(O(KN)\)，其中 \(K\) 为位数。

反思

赛时想这道题时，没有想到这个直接判断 \(\ge 10^{k+1}\)，而是把每一位拆开来看，看前面连续的和为 \(9\) 的进位。这样拆开使得计算冗杂，并且不好维护。

所以要换个角度再看一看问题。

代码

//none
#include<bits/stdc++.h>
#define int long long
#define ll long long
#define rep(i,n) for(int i=0;i<n;i++)
#define rept(i,n) for(int i=1;i<=n;i++)
#define repe(i,l,r) for(int i=l;i<=r;i++)
#define FOR(i,r,l) for(int i=r;i>=l;i--)
#define fi first
#define se second
#define pii pair<int,int>
#define mpr make_pair
#define pb push_back
#define sz(v) (int)(v.size())
using namespace std;
int read(){int sum=0,f=1;char c;c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){sum=(sum<<1)+(sum<<3)+(c-'0');c=getchar();}return sum*f;}
void out(int x){if(x<0){x=-x;putchar('-');}if(x>=10)out(x/10);putchar(x%10+'0');}
int fast(int a,int b,int P){int res=1;if(P<=0){while(b){if(b&1)res=res*a;a=a*a;b>>=1;}}else{while(b){if(b&1)res=res*a%P;a=a*a%P;b>>=1;}}return res;}
template<typename T>void chmax(T& a,T b){if(a<b)a=b;return;}
template<typename T>void chmin(T& a,T b){if(a>b)a=b;return;}
const int N=2e5+5;
int n,a[N],b[N][15],cur[N];
signed main(){
	n=read();
	int ans=0;
	rept(i,n){
		a[i]=read();
		rep(j,15){
			b[i][j]=a[i]%10;
			ans+=2*n*b[i][j];
			a[i]/=10;
		}
	}
	vector<int> vec;
	rep(i,15){
		vec.clear();
		rept(j,n){
			cur[j]+=b[j][i]*fast(10,i,0);
			vec.pb(cur[j]);
		}
		sort(vec.begin(),vec.end());
		rep(j,n){
			int pos=lower_bound(vec.begin(),vec.end(),fast(10,i+1,0)-vec[j])-vec.begin();
			ans-=(sz(vec)-pos)*9;
		}
	}
	out(ans);
	return 0;
}