一、题目
D2. Submarine in the Rybinsk Sea (hard edition)
二、分析
相比于简单版本，它的复杂地方在于对于不同长度，可能对每个点的贡献可能是有差异的。
但是，题目已经说明$a_{i}$最大知道10的9次方，那么$a_{i}$的长度最大也只有10，所以，我们可以按长度进行分组讨论。
需要注意的是，$a_{i}$确定了在前和在后并且确定了$f(a_{i},b_{i})$中的$b_{i}$的长度后，$a_{i}$对各个位置的贡献其实就确定了，相当于对于每一个$a_{i}$，我们最多求10次贡献就可以了。
三、AC代码
1 #include <bits/stdc++.h>
2
3 using namespace std;
4 typedef long long ll;
5 const int maxn = 1e5 + 14;
6 const int mod = 998244353;
7 int a[maxn], n;
8
9 int getlen(int data)
10 {
11 int len = 0;
12 while(data)
13 {
14 data/=10;
15 len++;
16 }
17 return len;
18 }
19
20 ll fun1(int x, int a, int b)
21 {
22 vector<int> vec, A(22, 0);
23 while(x)
24 {
25 vec.push_back(x % 10);
26 x /= 10;
27 }
28 reverse(vec.begin(), vec.end());
29 int _len = a + b;
30 if(a >= b)
31 {
32 auto itr = vec.begin();
33 for(int i = 1; i <= a - b + 1; i++)
34 {
35 A[i] = *itr;
36 itr++;
37 }
38 for(int i = a - b + 3; i <= _len; i += 2)
39 {
40 A[i] = *itr;
41 itr++;
42 }
43 }
44 else
45 {
46 auto itr = vec.begin();
47 for(int i = b - a + 1; i <= _len; i += 2)
48 {
49 A[i] = *itr;
50 itr++;
51 }
52 }
53 ll tot = 0;
54 for(int i = 0; i <= _len; i++)
55 {
56 tot = (tot * 10 + A[i]) % mod;
57 }
58 return tot;
59 }
60
61 ll fun2(int x, int b, int a)
62 {
63 vector<int> vec, A(22, 0);
64 while(x)
65 {
66 vec.push_back(x % 10);
67 x /= 10;
68 }
69 reverse(vec.begin(), vec.end());
70 int _len = a + b;
71 if(b <= a)
72 {
73 auto itr = vec.begin();
74 for(int i = 1; i <= a - b; i++)
75 {
76 A[i] = *itr;
77 itr++;
78 }
79 for(int i = a - b + 2; i <= _len; i += 2)
80 {
81 A[i] = *itr;
82 itr++;
83 }
84 }
85 else
86 {
87 auto itr = vec.begin();
88 for(int i = b - a + 2; i <= _len; i += 2)
89 {
90 A[i] = *itr;
91 itr++;
92 }
93 }
94 ll tot = 0;
95 for(int i = 0; i <= _len; i++)
96 {
97 tot = (tot * 10 + A[i]) % mod;
98 }
99 return tot;
100 }
101
102 int main()
103 {
104 while(scanf("%d", &n) != EOF)
105 {
106 ll ans = 0;
107 vector<int> vec[11];
108 for(int i = 0; i < n; i++)
109 {
110 scanf("%d", &a[i]);
111 vec[ getlen( a[i] ) ].push_back(a[i]);
112 }
113 for(int i = 1; i <= 10; i++)
114 {
115 for(auto itr : vec[i])
116 {
117 for(int j = 1; j <= 10; j++)
118 {
119 if( vec[j].size() )
120 {
121 ll res = 0;
122 int len = vec[j].size();
123 res = fun1(itr, i, j);
124 res = (res + fun2(itr, j, i)) % mod;
125 res = res * len % mod;
126 ans = (ans + res) % mod;
127 }
128 }
129 }
130 }
131 printf("%I64d\n", ans);
132 }
133 return 0;
134 }