Bình luận

• 
  

  -3

  

  vuongbankien012  đã bình luận lúc 7, Tháng 8, 2025, 2:22

  hint bài này:

  bài này mình sài đệ quy số lượng từng số, sài công thức chỉnh hợp để tính và khi đủ số sài dp để check,lưu ý những test lớn sẽ chạy hơi chậm 1 tí sẽ tle nên bạn hãy chạy tay và if test

  code tham khảo https://ideone.com/KcppmI

• 
  

  13

  

  KAKOII  đã bình luận lúc 30, Tháng 6, 2025, 12:09 ← sửa 6 →

  Ta giải quyết bài toán này bằng QHĐ chữ số:

  Ta có ~(idx, sum, possibleSum)~ lần lượt là các trạng thái: số thứ ~idx~ đang xét, tổng các chữ số trước và danh sách các tổng có thể hình thành từ những chữ số đã được điền.

  Khi ta điền số ~i~ (~0 \le i \le k~) vào vị trí ~idx~, việc chuyển trạng thái từ ~(idx, sum, possibleSum)~ sang ~(idx^*, sum^*, possibleSum^*)~ diễn ra như sau:

  • ~idx^*= idx - 1~
  • ~sum^* = sum + i~
  • ~possibleSum^* = possibleSum \cup \{x \in possibleSum \space | \space x + i\}~

  Khi ~idx < 0~:

  • Nếu ~sum~ lẻ thì số đó là một số không may mắn
  • Nếu ~sum~ chẵn thì số đó là một số không may mắn khi ~sum > 0~ và ~\frac{sum}{2} \notin possibleSum~

  Số lượng số không may mẵn có ~n~ chữ số và chỉ chứa các chữ số trong phạm vi từ ~0~ đến ~k~ bằng ~f(n - 1, 0, \{0\})~.

  Code hàm QHĐ chữ số hoạt động như sau:

  unordered_map<bitset<91>, __int128> memo[21][181];
  
  __int128 f(int idx, int sum, bitset<91> possum){
    if(idx < 0){
        if(sum & 1) return 1;
        return (sum > 0) && !possum[sum / 2];
    }
    if(memo[idx][sum].find(possum) != memo[idx][sum].end()) return memo[idx][sum][possum];
    __int128 ans = 0;
    for(int digit = 0; digit <= k; ++digit){
        ans += f(idx - 1, sum + digit, possum | (possum << digit));
    }
    return memo[idx][sum][possum] = ans;
  }