Bình luận

• 
  

  -3

  

  1213078273  đã bình luận lúc 15, Tháng 9, 2025, 3:33

  include<bits/stdc++.h>

  using namespace std;

  define el cout << "\n"

  define f0(i, n) for(int i = 0; i < n; ++i)

  define f1(i, n) for(int i = 1; i <= n; ++i)

  define maxn 1000006

  define MOD 1000000000

  int n, k, f[maxn];

  int main() { iosbase::syncwith_stdio(0); cin.tie(0); cout.tie(0);

  cin >> n >> k;
  
  // Base cases
  f[0] = 2; // For a string of length 0, there are two choices for the first bit (0 or 1)
  f[1] = 2; // For a string of length 1, both '0' and '1' are valid
  
  // Recurrence relation
  for (int i = 2; i <= n; i++)
  {
      // Total number of binary strings of length i is 2 * f[i-1].
      // This is because we can append either a '0' or a '1' to any valid string of length i-1.
      f[i] = (f[i-1] * 2) % MOD;
  
      // If the added bit is '0', we might create k+1 consecutive zeros.
      // We need to subtract the invalid strings.
      // An invalid string of length i ends in k+1 zeros. The rest of the string (length i-(k+1))
      // must be a valid string, and the (i-(k+1))th bit must be a '1' to break the sequence.
      // The number of such strings is f[i-k-2].
      // Wait, the logic is slightly different: the number of strings of length i-k-1
      // ending in a '1' is f[i-k-2]
  
      // Let's re-evaluate the recurrence:
      // f(i) = a(i) + b(i), where a(i) is strings ending in '0', b(i) is strings ending in '1'.
      // b(i) = f(i-1) (we can append '1' to any valid string of length i-1).
      // a(i) = b(i-1) + b(i-2) + ... + b(i-k)
      // This is not what the code implements. The provided code implements a different, but also valid, DP approach.
  
      // A more direct DP state:
      // f[i] = total valid strings of length i.
      // f[i] = (valid strings ending in 1) + (valid strings ending in 0).
      // Strings ending in 1: We can append '1' to any valid string of length i-1. Count = f[i-1].
      // Strings ending in 0: We can append '0' to any valid string of length i-1 as long as it doesn't create
      // k+1 consecutive zeros. This means we can append '0' to any string of length i-1 that doesn't
      // already end in k consecutive zeros.
  
      // Let's trace the code's logic, it's a bit more subtle but correct.
      // f[i-1] * 2 gives all binary strings of length i that are valid prefixes.
      // f[i] = f[i-1] (append '1') + f[i-1] (append '0').
      // If we append '0', we must subtract cases where we create k+1 zeros.
      // An invalid string is of the form: (valid string of length i-k-1) + '1' + '0' * (k+1).
      // The number of valid strings of length i-k-1 is f[i-k-1].
      // So, we need to subtract f[i-k-1].
  
      if (i > k) {
          f[i] = (f[i] - f[i-k-1]) % MOD;
      }
  
      f[i] = (f[i] + MOD) % MOD; // Handle negative results of modulo
  }
  
  cout << f[n] << endl;
  
  return 0;
  

  }

• 
  

  -11

  

  chunguyen2k8  đã bình luận lúc 27, Tháng 5, 2024, 9:36

  xin down vote

  Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

• 
  

  -8

  

  chunguyen2k8  đã bình luận lúc 27, Tháng 5, 2024, 9:36

  Đề xuất thêm tag nhân ma trận

  Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

• 
  

  21

  

  dlbm1302  đã bình luận lúc 4, Tháng 2, 2022, 16:53 ← chỉnh sửa →

  Em đề xuất thêm tag quy hoạch động cho bài này ạ