fork download
copy 
  1.  
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4.  
  5. #define MOD 998244353
  6.  
  7. int bp(int a, int b) {
  8. 	if (! b) return 1;
  9. 	int r = bp(a, b >> 1);
  10. 	if ((b & 1)) return (long long)r * r % MOD * a % MOD;
  11. 	return (long long)r * r % MOD;
  12. }
  13.  
  14. #define A 45
  15. #define N 250005
  16.  
  17. int inv[A], p[N], ip[N], a[N], n
  18. 	, dp[N], mm[A], cc[A]
  19. 	, cnt[N], cntby[A]
  20. 	;
  21.  
  22. int main() {
  23. 	scanf("%d", &n);
  24. 	for (int i = 0; i < A; ++i)
  25. 		inv[i] = bp(i, MOD - 2);
  26. 	p[0] = ip[0] = 1;
  27. 	for (int i = 1; i <= n; ++i) {
  28. 		scanf("%d", a + i);
  29. 		p[i] = (long long)p[i - 1] * a[i] % MOD;
  30. 		ip[i] = (long long)ip[i - 1] * inv[a[i]] % MOD;
  31. 	}
  32.  
  33. 	cnt[0] = 1;
  34. 	for (int i = 1; i <= n; ++i) {
  35. 		cntby[a[i]] = (cntby[a[i]] + cnt[i - 1]) % MOD;
  36. 		mm[a[i]] = (mm[a[i]] + (long long)ip[i - 1] * cnt[i - 1] % MOD) % MOD;
  37. 		cc[a[i]] = (cc[a[i]] + dp[i - 1]) % MOD;
  38. 		dp[i] = ((long long)mm[a[i]] * p[i] % MOD + cc[a[i]]) % MOD;
  39. 		cnt[i] = cntby[a[i]];
  40. 	}
  41. 	printf("%d\n", dp[n]);
  42.  
  43. 	return 0;
  44. }
  45.  
  46.  
Success #stdin #stdout 0s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/uDGV9f
language:
C++14 (gcc 8.3)
created:
7 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!