fork download
copy 
  1. #include <bits/stdc++.h> 
  2.  
  3. using namespace std;  
  4.  
  5. typedef long long ll;  
  6. typedef pair<int, int> ii;  
  7.  
  8. const int INF = 1e9;  
  9. const ll LINF = 1e18;  
  10.  
  11. const int MOD = 998244353;  
  12.  
  13. void add(int& a, int b) {
  14. 	a += b; 
  15. 	if (a >= MOD) a -= MOD;
  16. 	if (a < 0) a += MOD; 
  17. }
  18.  
  19. int n;  
  20. string s[23];
  21.  
  22. int cnt[23][26];
  23. int sum_idx[1 << 23]; 
  24. int min_cnt[1 << 23][26];
  25. int sos[1 << 23]; 
  26.  
  27. int sign(int mask) {
  28. 	return (__builtin_parity(mask) ? 1 : -1);
  29. }
  30.  
  31. int main() {
  32. 	ios::sync_with_stdio(false); 
  33. 	cin.tie(nullptr); 	
  34. 	cin >> n;
  35. 	for (int i = 0; i < n; i++) cin >> s[i]; 
  36.  
  37. 	for (int i = 0; i < n; i++) {
  38. 		for (char c : s[i]) ++cnt[i][c - 'a'];
  39. 	}	
  40.  
  41. 	sum_idx[0] = 0;
  42. 	for (int c = 0; c <= 25; c++) min_cnt[0][c] = INF;
  43. 	for (int mask = 1; mask < (1 << n); mask++) {
  44. 		int i = __builtin_ctz(mask);   
  45. 		sum_idx[mask] = sum_idx[mask ^ (1 << i)] + (i + 1);  
  46. 		for (int c = 0; c <= 25; c++) {
  47. 			min_cnt[mask][c] = min(min_cnt[mask ^ (1 << i)][c], cnt[i][c]);
  48. 		}
  49. 	}
  50.  
  51. 	for (int mask = 1; mask < (1 << n); mask++) {
  52. 		sos[mask] = 1; 
  53. 		for (int c = 0; c <= 25; c++) {
  54. 			sos[mask] = 1ll * sos[mask] * (min_cnt[mask][c] + 1) % MOD; 
  55. 		}
  56. 	}
  57.  
  58. 	for (int mask = 0; mask < (1 << n); mask++) {
  59. 		sos[mask] = sign(mask) * sos[mask];
  60. 	}	
  61.  
  62. 	for (int i = 0; i < n; i++) {
  63. 		for (int mask = 0; mask < (1 << n); mask++) {
  64. 			if (mask & (1 << i)) add(sos[mask], sos[mask ^ (1 << i)]);
  65. 		}
  66. 	}
  67.  
  68. 	ll ans = 0;   
  69. 	for (int mask = 0; mask < (1 << n); mask++) {
  70. 		if (sos[mask] < 0) sos[mask] += MOD; 
  71. 		int k = __builtin_popcount(mask);
  72. 		ans ^= 1ll * sos[mask] * k * sum_idx[mask];
  73. 	}
  74.  
  75. 	cout << ans << '\n';
  76. }
Success #stdin #stdout 0.01s 7704KB
comments (?)
stdin
copy 
3
ddd
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaabbbbbbbbbbbcccccccccccciiiiiiiiiiiiiiiiiiiiiiooooooooooqqqqqqqqqqqqqqqqqqvvvvvzzzzzzzzzzzz
stdout
copy 
15706243380
https://ideone.com/z3yAB5
language:
C++14 (gcc 8.3)
created:
11 days ago
visibility:
secret

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!