Carries

frog has $n$

Unfortunately, frog is somehow afraid of carries (进位). She defines hardness $h (x, y)$

Find the total hardness adding $n$

\sum 1 \leq i < j \leq n h (a i, a j)

Input

The input consists of multiple tests. For each test:

The first line contains $1$

Output

For each test, write $1$

Sample Input

2
5 5
10
0 1 2 3 4 5 6 7 8 9

Sample Output

1
20


//题意: n 个数，C(n,2) 这两个数可能进位，问，所有的进位次数是多少?


//题解: 容易想到，枚举可能进位的位置，最多也就9次么，然后二分找可能进位的个数
答案要LL，还wa了一发

 1 # include <cstdio>
 2 # include <cstring>
 3 # include <cstdlib>
 4 # include <iostream>
 5 # include <vector>
 6 # include <queue>
 7 # include <stack>
 8 # include <map>
 9 # include <bitset>
10 # include <sstream>
11 # include <set>
12 # include <cmath>
13 # include <algorithm>
14 #pragma comment(linker,"/STACK:102400000,102400000")
15 using namespace std;
16 #define LL          long long
17 #define lowbit(x)   ((x)&(-x))
18 #define PI          acos(-1.0)
19 #define INF         0x3f3f3f3f
20 #define eps         1e-8
21 #define MOD         1000000007
22 
23 inline int scan() {
24     int x=0,f=1; char ch=getchar();
25     while(ch<'0'||ch>'9'){if(ch=='-') f=-1; ch=getchar();}
26     while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}
27     return x*f;
28 }
29 inline void Out(int a) {
30     if(a<0) {putchar('-'); a=-a;}
31     if(a>=10) Out(a/10);
32     putchar(a%10+'0');
33 }
34 #define MX 100005
35 /**************************/
36 int n;
37 int a[MX];
38 int yu[MX];
39 
40 int bi_search(int l,int r,int w)
41 {
42     int pos = -1;
43     while (l<=r)
44     {
45         int mid = (l+r)/2;
46         if (yu[mid]>=w)
47         {
48             pos = mid;
49             r = mid-1;
50         }
51         else l = mid+1;
52     }
53     return pos;
54 }
55 
56 int main()
57 {
58     while (scanf("%d",&n)!=EOF)
59     {
60         int mmm=0;
61         for (int i=1;i<=n;i++)
62         {
63             a[i] =scan();
64             mmm = max(mmm,a[i]);
65         }
66         LL ans = 0;
67         int y = 1;
68         while(y)
69         {
70             y*=10;
71             for (int i=1;i<=n;i++)
72                 yu[i] = a[i]%y;
73             sort(yu+1,yu+1+n);
74             for (int i=1;i<=n;i++)
75             {
76                 int pos = bi_search(1,n,y-(a[i]%y));
77                 if (pos!=-1)
78                 {
79                     int num = n-pos+1;
80                     if (a[i]%y<yu[pos]) ans += (LL)num;
81                     else ans += (LL)num-1;
82                 }
83             }
84             if (y>mmm) break;
85         }
86         printf("%lld
",ans/2);
87     }
88     return 0;
89 }

View Code