fork download
copy 
  1. /*
  2. PROBLEM: Count Valid Strings with Forbidden Adjacent Pairs
  3.  
  4. Given:
  5. - N: length of string to generate
  6. - M: number of forbidden adjacent character pairs
  7.  
  8. Task: Count strings of length N using letters 'a'-'z' where no two adjacent 
  9. characters form a forbidden pair.
  10.  
  11. Key Insight:
  12. - If two characters are in a "forbidden pair", they cannot be next to each other
  13. - Use Dynamic Programming with matrix exponentiation
  14. - Group forbidden characters together using Union-Find
  15. - Characters can follow each other ONLY if they're the same OR in different groups
  16.  
  17. Example:
  18. N=3, M=1, forbidden pair: (a,b)
  19. - "abc" is invalid (a followed by b)
  20. - "bac" is invalid (b followed by a) 
  21. - "aac" is valid
  22. - "cde" is valid
  23.  
  24. Approach:
  25. 1. Group characters that can't be adjacent using Union-Find
  26. 2. Build transition matrix: can character i be followed by character j?
  27. 3. Use matrix exponentiation to count all valid paths of length N
  28. 4. Sum all entries in result matrix
  29.  
  30. Time: O(T * (M + 26³ * log N))
  31. */
  32.  
  33. #include <bits/stdc++.h>
  34. using namespace std;
  35.  
  36. const long long MOD = 1e9 + 7;
  37.  
  38. // Union-Find: keeps track of which characters are in the same "forbidden group"
  39. struct UF {
  40.     int p[26];  // parent of each character
  41.     int r[26];  // rank for union by rank optimization
  42.  
  43.     UF() {
  44.         // Initially each character is its own parent
  45.         for (int i = 0; i < 26; i++) {
  46.             p[i] = i;
  47.             r[i] = 0;
  48.         }
  49.     }
  50.  
  51.     // Find the root/leader of the group containing x
  52.     int find(int x) {
  53.         // Path compression: make all nodes point directly to root
  54.         if (p[x] != x) p[x] = find(p[x]);
  55.         return p[x];
  56.     }
  57.  
  58.     // Merge two groups together
  59.     void join(int x, int y) {
  60.         int rx = find(x);  // root of x's group
  61.         int ry = find(y);  // root of y's group
  62.  
  63.         if (rx == ry) return;  // already in same group
  64.  
  65.         // Union by rank: attach smaller tree under larger tree
  66.         if (r[rx] < r[ry]) swap(rx, ry);
  67.         p[ry] = rx;
  68.         if (r[rx] == r[ry]) r[rx]++;
  69.     }
  70. };
  71.  
  72. // Matrix for counting transitions between characters
  73. struct Mat {
  74.     long long m[26][26];
  75.  
  76.     Mat(bool id = false) {
  77.         // Initialize all entries to 0
  78.         for (int i = 0; i < 26; i++) {
  79.             for (int j = 0; j < 26; j++) {
  80.                 m[i][j] = 0;
  81.             }
  82.         }
  83.         // If identity matrix requested, set diagonal to 1
  84.         if (id) {
  85.             for (int i = 0; i < 26; i++) m[i][i] = 1;
  86.         }
  87.     }
  88. };
  89.  
  90. // Multiply two matrices (standard matrix multiplication)
  91. Mat mult(Mat a, Mat b) {
  92.     Mat res;
  93.  
  94.     for (int i = 0; i < 26; i++) {
  95.         for (int j = 0; j < 26; j++) {
  96.             // Compute res[i][j] = sum of a[i][k] * b[k][j]
  97.             for (int k = 0; k < 26; k++) {
  98.                 res.m[i][j] = (res.m[i][j] + a.m[i][k] * b.m[k][j]) % MOD;
  99.             }
  100.         }
  101.     }
  102.  
  103.     return res;
  104. }
  105.  
  106. // Fast exponentiation: compute matrix^n in O(log n) time
  107. Mat pow(Mat a, long long n) {
  108.     Mat res(true);  // Start with identity matrix
  109.  
  110.     while (n > 0) {
  111.         // If n is odd, multiply result by current matrix
  112.         if (n & 1) res = mult(res, a);
  113.  
  114.         // Square the matrix
  115.         a = mult(a, a);
  116.  
  117.         // Divide n by 2
  118.         n >>= 1;
  119.     }
  120.  
  121.     return res;
  122. }
  123.  
  124. int main() {
  125.     ios::sync_with_stdio(false);
  126.     cin.tie(nullptr);
  127.  
  128.     int t;
  129.     cin >> t;
  130.  
  131.     while (t--) {
  132.         long long n;  // string length
  133.         int m;        // number of forbidden pairs
  134.         cin >> n >> m;
  135.  
  136.         // Build union-find structure
  137.         // Characters in same group cannot be adjacent
  138.         UF uf;
  139.  
  140.         for (int i = 0; i < m; i++) {
  141.             char a, b;
  142.             cin >> a >> b;
  143.             // Put a and b in same group (they're forbidden to be adjacent)
  144.             uf.join(a - 'a', b - 'a');
  145.         }
  146.  
  147.         // Edge case: empty string has exactly 1 way (the empty string itself)
  148.         if (n == 0) {
  149.             cout << 1 << "\n";
  150.             continue;
  151.         }
  152.  
  153.         // Edge case: single character can be any of 26 letters
  154.         if (n == 1) {
  155.             cout << 26 << "\n";
  156.             continue;
  157.         }
  158.  
  159.         // Build transition matrix
  160.         // trans[i][j] = 1 means character i can be followed by character j
  161.         Mat trans;
  162.  
  163.         for (int i = 0; i < 26; i++) {
  164.             for (int j = 0; j < 26; j++) {
  165.                 // Characters can be adjacent if:
  166.                 // 1. They are the same character (i == j), OR
  167.                 // 2. They belong to different forbidden groups
  168.                 if (i == j || uf.find(i) != uf.find(j)) {
  169.                     trans.m[i][j] = 1;
  170.                 }
  171.             }
  172.         }
  173.  
  174.         // Matrix exponentiation to count paths
  175.         // trans^(n-1) gives us count of all valid sequences of length n
  176.         // Why n-1? First character is "free", then we make n-1 transitions
  177.         Mat res = pow(trans, n - 1);
  178.  
  179.         // Sum all entries in result matrix
  180.         // res[i][j] = number of valid strings starting with char i and ending with char j
  181.         // Total answer = sum over all possible (start, end) pairs
  182.         long long ans = 0;
  183.         for (int i = 0; i < 26; i++) {
  184.             for (int j = 0; j < 26; j++) {
  185.                 ans = (ans + res.m[i][j]) % MOD;
  186.             }
  187.         }
  188.  
  189.         cout << ans << "\n";
  190.     }
  191.  
  192.     return 0;
  193. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/9FEQiV
language:
C++14 (gcc 8.3)
created:
1 day 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!