Guest User

Untitled

a guest
Jan 24th, 2020
780
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2. It assumes the input comes in the format
  3.  
  4. <target string>
  5. <number of strings you can select characters from>
  6. <string 1>
  7. ...
  8. <string n>
  9.  
  10. Where each string has length at most 20
  11.  */
  12.  
  13. #include <bits/stdc++.h>
  14.  
  15. using namespace std;
  16.  
  17. int64_t n;
  18. string target;
  19. string s;
  20. int64_t MOD = 1000000007;
  21.  
  22. int main() {
  23.   ios_base::sync_with_stdio(false);
  24.   cin.tie(0);
  25.   cin >> target >> n;
  26.   map<pair<int64_t, char>, int64_t> chars_per_pos;
  27.   for (int64_t i = 0; i < n; i++) {
  28.     cin >> s;
  29.     for (int64_t j = 0; j < s.size(); j++) {
  30.       chars_per_pos[{j, s[j]}]++;
  31.     }
  32.   }
  33.   int64_t total = 0;
  34.   for (int64_t mask = 0; mask < (1 << 20); mask++) {
  35.     if (__builtin_popcount(mask) != target.size()) {
  36.       continue;
  37.     }
  38.     int64_t idx = 0;
  39.     int64_t temp = 1;
  40.     for (int64_t j = 0; j < 20; j++) {
  41.       if (mask & (1 << j)) {
  42.         temp = (temp * chars_per_pos[{j, target[idx]}]) % MOD;
  43.         idx++;
  44.       }
  45.     }
  46.     total = (total + temp) % MOD;
  47.   }
  48.   cout << total << '\n';
  49. }
RAW Paste Data