fork download
copy 
  1. /*
  2. QUESTION 9: Odd Parts with Blocked Prefix Values
  3.  
  4. Problem Statement:
  5. You are given a target sum X and a list of forbidden numbers.
  6.  
  7. Count how many sequences of positive odd integers have total sum exactly X.
  8.  
  9. While reading the sequence from left to right, no prefix sum is allowed to be equal
  10. to any forbidden number.
  11.  
  12. Return the count modulo 998244353.
  13.  
  14. Hard Constraints:
  15. 1 <= X <= 1e18
  16. 1 <= number of forbidden values <= 100000
  17. 1 <= forbidden[i] <= 1e18
  18.  
  19. Example:
  20. X = 6
  21. forbidden = [1, 4]
  22.  
  23. Expected Output:
  24. 2
  25.  
  26. Explanation:
  27. Valid sequences:
  28. [3, 3]
  29. [5, 1]
  30.  
  31. Invalid:
  32. [1, 5] because prefix sum 1 is forbidden.
  33. [3, 1, 1, 1] because prefix sum 4 is forbidden.
  34.  
  35. Brute Force:
  36. Generate all ways to write X as a sum of positive odd numbers.
  37. Check prefix sums for every sequence.
  38.  
  39. Time Complexity:
  40. Exponential
  41.  
  42. Optimized Approach:
  43. Let dp[s] be the number of ways to reach prefix sum s.
  44.  
  45. Since every added number is odd:
  46. previous prefix and current prefix must have opposite parity.
  47.  
  48. Maintain:
  49. evenSum = total ways ending at even prefix sums
  50. oddSum = total ways ending at odd prefix sums
  51.  
  52. If a prefix sum is forbidden, skip it.
  53.  
  54. Because X can be very large, process long allowed ranges using matrix exponentiation.
  55.  
  56. Time Complexity:
  57. O(N log N + N log X)
  58.  
  59. Space Complexity:
  60. O(N)
  61. */
  62.  
  63. #include <bits/stdc++.h>
  64. using namespace std;
  65.  
  66. class Solution {
  67. public:
  68.     static const long long MOD = 998244353;
  69.  
  70.     struct Matrix {
  71.         long long a[2][2];
  72.  
  73.         Matrix(long long a00 = 1, long long a01 = 0,
  74.                long long a10 = 0, long long a11 = 1) {
  75.             a[0][0] = a00;
  76.             a[0][1] = a01;
  77.             a[1][0] = a10;
  78.             a[1][1] = a11;
  79.         }
  80.     };
  81.  
  82.     Matrix multiply(Matrix x, Matrix y) {
  83.         Matrix res(0, 0, 0, 0);
  84.  
  85.         for (int i = 0; i < 2; i++) {
  86.             for (int j = 0; j < 2; j++) {
  87.                 for (int k = 0; k < 2; k++) {
  88.                     res.a[i][j] =
  89.                         (res.a[i][j] + x.a[i][k] * y.a[k][j]) % MOD;
  90.                 }
  91.             }
  92.         }
  93.  
  94.         return res;
  95.     }
  96.  
  97.     Matrix power(Matrix base, long long exp) {
  98.         Matrix res;
  99.  
  100.         while (exp > 0) {
  101.             if (exp & 1) res = multiply(res, base);
  102.             base = multiply(base, base);
  103.             exp >>= 1;
  104.         }
  105.  
  106.         return res;
  107.     }
  108.  
  109.     pair<long long, long long> apply(Matrix m, long long evenSum, long long oddSum) {
  110.         long long newEven =
  111.             (m.a[0][0] * evenSum + m.a[0][1] * oddSum) % MOD;
  112.  
  113.         long long newOdd =
  114.             (m.a[1][0] * evenSum + m.a[1][1] * oddSum) % MOD;
  115.  
  116.         return {newEven, newOdd};
  117.     }
  118.  
  119.     void processRange(long long l,
  120.                       long long r,
  121.                       long long& evenSum,
  122.                       long long& oddSum) {
  123.         if (l > r) return;
  124.  
  125.         long long len = r - l + 1;
  126.  
  127.         Matrix oddStep(1, 0, 1, 1);
  128.         Matrix evenStep(1, 1, 0, 1);
  129.  
  130.         Matrix pairStep;
  131.         Matrix singleStep;
  132.  
  133.         if (l % 2 == 1) {
  134.             pairStep = multiply(evenStep, oddStep);
  135.             singleStep = oddStep;
  136.         } else {
  137.             pairStep = multiply(oddStep, evenStep);
  138.             singleStep = evenStep;
  139.         }
  140.  
  141.         Matrix jump = power(pairStep, len / 2);
  142.  
  143.         auto p = apply(jump, evenSum, oddSum);
  144.         evenSum = p.first;
  145.         oddSum = p.second;
  146.  
  147.         if (len % 2 == 1) {
  148.             p = apply(singleStep, evenSum, oddSum);
  149.             evenSum = p.first;
  150.             oddSum = p.second;
  151.         }
  152.     }
  153.  
  154.     long long countValidSequences(int N, long long X, vector<long long>& A) {
  155.         vector<long long> blocked;
  156.  
  157.         for (long long v : A) {
  158.             if (v == X) return 0;
  159.  
  160.             if (v > 0 && v < X) {
  161.                 blocked.push_back(v);
  162.             }
  163.         }
  164.  
  165.         sort(blocked.begin(), blocked.end());
  166.         blocked.erase(unique(blocked.begin(), blocked.end()), blocked.end());
  167.  
  168.         long long evenSum = 1;
  169.         long long oddSum = 0;
  170.  
  171.         long long current = 1;
  172.  
  173.         for (long long b : blocked) {
  174.             processRange(current, b - 1, evenSum, oddSum);
  175.             current = b + 1;
  176.         }
  177.  
  178.         processRange(current, X - 1, evenSum, oddSum);
  179.  
  180.         if (X % 2 == 1) return evenSum;
  181.         return oddSum;
  182.     }
  183. };
  184.  
  185. int main() {
  186.     Solution sol;
  187.  
  188.     long long X = 6;
  189.     vector<long long> forbidden = {1, 4};
  190.  
  191.     cout << sol.countValidSequences((int)forbidden.size(), X, forbidden) << endl;
  192.  
  193.     return 0;
  194. }
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
2
https://ideone.com/wxpFqW
language:
C++14 (gcc 8.3)
created:
9 hours 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!