Advertisement
Guest User

Untitled

a guest
Jul 17th, 2019
82
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.81 KB | None | 0 0
  1. import java.util.*;
  2. import java.io.*;
  3.  
  4. public class D {
  5.  
  6. static final boolean stdin = true;
  7. static final String filename = "";
  8. static FastScanner br;
  9. static PrintWriter pw;
  10.  
  11. public static void main(String[] args) throws IOException {
  12.  
  13. if (stdin) {
  14. br = new FastScanner();
  15. pw = new PrintWriter(new OutputStreamWriter(System.out));
  16. } else {
  17. br = new FastScanner(filename + ".in");
  18. pw = new PrintWriter(new FileWriter(filename + ".out"));
  19. }
  20.  
  21. Solver solver = new Solver();
  22. solver.solve(br, pw);
  23. }
  24.  
  25. static class Solver {
  26. static long mod = 998244353L;
  27.  
  28. public void solve(FastScanner br, PrintWriter pw) throws IOException {
  29.  
  30. //initialization of array storing each of the given numbers
  31. //initialization of array storing the counts of each size number
  32. int n = br.nextInt();
  33. long[] vals = new long[n];
  34. long[] cnts = new long[11];
  35.  
  36. //storing all the numbers and their respective lengths
  37. for (int i = 0; i < n; i++) {
  38. long l = br.nextLong();
  39. vals[i] = l;
  40. int counter = 0;
  41. while (l != 0L) {
  42. l = l / 10;
  43. counter++;
  44. }
  45. cnts[counter]++;
  46. }
  47.  
  48. //looping through each number (vals[i]) and size of each number in vals (j)
  49. long out = 0;
  50. for (int i = 0; i < n; i++) {
  51. for (int j = 1; j < 11; j++) {
  52.  
  53. //skip if there are no numbers of size j
  54. if(cnts[j]==0)
  55. continue;
  56.  
  57. //initialization
  58. int counter = 0;
  59. long l = vals[i];
  60. long a = 0; //stores number where 0 is not put in ones place
  61. long b = 0; //stores number where 0 is put in ones place
  62.  
  63. //for every digit in the number up to j starting from ones place
  64. //put in 0s at appropriate places and keep the total
  65. while (l != 0L && counter < j) {
  66. a += ((l % 10) * (pow(10, counter * 2)) % mod) % mod;
  67. b += ((l % 10) * (pow(10, (counter) * 2 + 1)) % mod) % mod;
  68. l /= 10;
  69. counter++;
  70. }
  71.  
  72. //after the rightmost j digits, keep the rest of the left digits the same
  73. counter *= 2;
  74. a += (l * (pow(10, counter)) % mod) % mod;
  75. b += (l * (pow(10, counter)) % mod) % mod;
  76.  
  77. //System.out.println("A " + a + ": " + j + " " + cnts[j]);
  78. //System.out.println("B " + b + ": " + j + " " + cnts[j]);
  79.  
  80. //store these modified numbers * # of times they will be needed
  81. out += (a*cnts[j])%mod;
  82. out %= mod;
  83. out += (b*cnts[j])%mod;
  84. out %= mod;
  85. }
  86. }
  87.  
  88. //output
  89. pw.println(out % mod);
  90. pw.close();
  91. }
  92.  
  93. //fast exponent
  94. static long pow(long a, long b) {
  95. if (b == 0)
  96. return 1L;
  97. long val = pow(a, b / 2);
  98. if (b % 2 == 0)
  99. return val * val % mod;
  100. else
  101. return val * val % mod * a % mod;
  102. }
  103.  
  104. }
  105.  
  106. static class Point implements Comparable<Point> {
  107. int a;
  108. int b;
  109.  
  110. Point(int a, int b) {
  111. this.a = a;
  112. this.b = b;
  113. }
  114.  
  115. @Override
  116. public int compareTo(Point o) {
  117. return this.a - o.a;
  118. }
  119.  
  120. }
  121.  
  122. static class Dsu {
  123. int n;
  124. int[] parent;
  125. int[] rank;
  126.  
  127. public Dsu(int n) {
  128. this.n = n;
  129. parent = new int[n];
  130. rank = new int[n];
  131. }
  132.  
  133. public void createSet() {
  134. for (int i = 0; i < n; i++) {
  135. parent[i] = i;
  136. rank[i] = 0;
  137. }
  138. }
  139.  
  140. public int findParent(int x) {
  141. if (parent[x] == x)
  142. return x;
  143. parent[x] = findParent(parent[x]);
  144. return parent[x];
  145. }
  146.  
  147. public void mergeSet(int a, int b) {
  148. int pa = findParent(a);
  149. int pb = findParent(b);
  150.  
  151. if (pa == pb)
  152. return;
  153.  
  154. if (rank[pa] > rank[pb]) {
  155. parent[pb] = pa;
  156. } else if (rank[pa] < rank[pb]) {
  157. parent[pa] = pb;
  158. } else {
  159. parent[pb] = pa;
  160. rank[pa]++;
  161. }
  162. }
  163. }
  164.  
  165. public static class FastScanner {
  166. BufferedReader br;
  167. StringTokenizer st;
  168.  
  169. public FastScanner(String s) {
  170. try {
  171. br = new BufferedReader(new FileReader(s));
  172. } catch (FileNotFoundException e) {
  173. e.printStackTrace();
  174. }
  175. }
  176.  
  177. public FastScanner() {
  178. br = new BufferedReader(new InputStreamReader(System.in));
  179. }
  180.  
  181. String nextToken() {
  182. while (st == null || !st.hasMoreElements()) {
  183. try {
  184. st = new StringTokenizer(br.readLine());
  185. } catch (IOException e) {
  186. e.printStackTrace();
  187. }
  188. }
  189. return st.nextToken();
  190. }
  191.  
  192. int nextInt() {
  193. return Integer.parseInt(nextToken());
  194. }
  195.  
  196. long nextLong() {
  197. return Long.parseLong(nextToken());
  198. }
  199.  
  200. double nextDouble() {
  201. return Double.parseDouble(nextToken());
  202. }
  203.  
  204. ArrayList<Integer>[] nextGraph(int nodes, int edges) {
  205. ArrayList<Integer>[] adj = new ArrayList[nodes];
  206. for (int i = 0; i < nodes; i++) {
  207. adj[i] = new ArrayList<Integer>();
  208. }
  209. for (int i = 0; i < edges; i++) {
  210. int a = nextInt() - 1;
  211. int b = nextInt() - 1;
  212. adj[a].add(b);
  213. adj[b].add(a);
  214. }
  215. return adj;
  216. }
  217. }
  218. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement