题意：问任意两对ai，aj相加的总进位数为多少。比如5,6,95分为（5,6）（5,95）（6,95），进位数 = 1 + 2 + 2 = 5
思路：显然暴力是会超时的。我们可以知道总进位数等于每一位进位数之和，所以我们可以把10个位数的进位分开算，每次%10^k，排序后用二分找到刚好的位置，然后算总数。
好像是唯一一次写二分一次A的题。
代码：
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<stdio.h>
#include<string.h>
#include<queue>
#include<cmath>
#include<map>
#include<set>
#include<vector>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + ;
const ll seed = ;
ll a[maxn], b[maxn], k;
ll fac[];
int mid(int l, int r, ll num){
int m, ans = r + ;
while(l <= r){
m = (l + r) >> ;
if(num + b[m] >= fac[k]) ans = m;
if(num + b[m] < fac[k]) l = m + ;
else r = m - ;
}
return ans;
}
int main(){
int n;
fac[] = ;
for(int i = ; i <= ; i++)
fac[i] = fac[i - ] * ;
while(~scanf("%d", &n)){
k = ;
ll ans = ;
for(int i = ; i <= n; i++)
scanf("%lld", &a[i]);
for(int i = ; i <= ; i++){
k = i;
for(int i = ; i <= n; i++)
b[i] = a[i] % fac[k];
sort(b + , b + n + );
for(int i = ; i <= n; i++){
int pos = mid(i + , n, b[i]);
ans += (n - pos + );
}
}
printf("%lld\n", ans);
}
return ;
}