Bình luận

• 
  

  1

  

  deanqkhanh  đã bình luận lúc 28, Tháng 12, 2025, 5:43

  Nhận xét ban đầu

  • Nếu N lẻ → không thể có số lượng 0 = 1 → đáp án = 0
  • Nếu K = 0 → không tồn tại số chia hết cho 0 → đáp án = 0

  Từ đây, giả sử:

  N chẵn, K ≥ 1
  

  ---

  Ý tưởng chính

  Ta xây dựng xâu nhị phân từ trái sang phải. Khi thêm một bit b ∈ {0,1} vào cuối một số nhị phân hiện tại có giá trị mod:

  new_mod = (mod * 2 + b) % K
  

  Do cần kiểm soát số lượng bit 1, ta dùng DP theo vị trí + số bit 1 + modulo.

  ---

  Định nghĩa DP

  Gọi:

  dp[pos][one][mod]
  

  Trong đó:

  • pos : đã đặt pos bit (0 → N)
  • one : số bit 1 đã dùng
  • mod : giá trị hiện tại modulo K

  Suy ra:

  zero = pos - one
  

  ---

  Điều kiện hợp lệ

  • one ≤ N/2
  • zero ≤ N/2
  • pos = 0 → không được đặt bit 0 (tránh số có 0 ở đầu)

  ---

  Chuyển trạng thái

  Tại dp[pos][one][mod]:

  Đặt bit 1

  Nếu one + 1 ≤ N/2:

  dp[pos+1][one+1][ (mod*2 + 1) % K ] += dp[pos][one][mod]
  

  Đặt bit 0

  Nếu pos > 0 và zero + 1 ≤ N/2:

  dp[pos+1][one][ (mod*2) % K ] += dp[pos][one][mod]
  

  ---

  Trạng thái khởi đầu & kết thúc

  • Khởi đầu:

    dp[0][0][0] = 1
    

  • Kết quả cần tìm:

    dp[N][N/2][0]
    

  ---

  Tính đúng đắn

  • DP duyệt mọi xâu nhị phân hợp lệ độ dài N
  • Điều kiện one ≤ N/2, zero ≤ N/2 đảm bảo đúng số lượng bit
  • Công thức modulo đảm bảo giá trị nhị phân được tính chính xác
  • Chỉ đếm những xâu có mod = 0 ⇒ chia hết cho K

  ⇒ DP đếm đúng và đủ

  ---

  Độ phức tạp

  • Số trạng thái:

    N × (N/2) × K ≤ 64 × 32 × 100 ≈ 2×10^5
    

  • Mỗi trạng thái O(1)

  Chạy rất nhanh

  ---

  Code C++ hoàn chỉnh

  #include <bits/stdc++.h>
  using namespace std;
  using ll = long long;
  
  int main(){
      ios::sync_with_stdio(false);
      cin.tie(nullptr);
  
      int N, K;
      cin >> N >> K;
  
      // Trường hợp vô nghiệm
      if (N % 2 == 1 || K == 0){
          cout << 0 << '\n';
          return 0;
      }
  
      static ll dp[65][33][101];
      memset(dp, 0, sizeof(dp));
  
      // Khởi tạo
      dp[0][0][0] = 1;
  
      for (int pos = 0; pos < N; ++pos){
          for (int one = 0; one <= N/2; ++one){
              int zero = pos - one;
              if (zero < 0 || zero > N/2) continue;
  
              for (int mod = 0; mod < K; ++mod){
                  ll cur = dp[pos][one][mod];
                  if (!cur) continue;
  
                  // Đặt bit 1
                  if (one + 1 <= N/2){
                      int nmod = (mod * 2 + 1) % K;
                      dp[pos + 1][one + 1][nmod] += cur;
                  }
  
                  // Đặt bit 0 (không ở đầu)
                  if (pos > 0 && zero + 1 <= N/2){
                      int nmod = (mod * 2) % K;
                      dp[pos + 1][one][nmod] += cur;
                  }
              }
          }
      }
  
      cout << dp[N][N/2][0] << '\n';
      return 0;
  }