結果
| 問題 |
No.822 Bitwise AND
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:15:34 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 7,821 bytes |
| コンパイル時間 | 871 ms |
| コンパイル使用メモリ | 83,972 KB |
| 実行使用メモリ | 7,848 KB |
| 最終ジャッジ日時 | 2025-05-14 13:16:39 |
| 合計ジャッジ時間 | 1,612 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 10 WA * 7 |
ソースコード
#include <iostream>
#include <vector>
#include <map>
#include <tuple> // Include tuple for map key
// Use long long for potentially large counts, although intermediate values might not exceed standard int ranges.
using namespace std;
// Global variables to store input N and K
long long N_param, K_param;
// Memoization table using std::map. The key is a tuple representing the DP state (bit, tight_k, current_borrow).
// The value is the computed count for that state.
map<tuple<int, bool, bool>, long long> memo;
/**
* Recursive function with memoization implementing the Digit DP approach.
* It counts the number of pairs (x, y) satisfying the problem conditions.
*
* @param bit The current bit position being considered (processing from most significant bit, e.g., 59, down to least significant bit, 0).
* @param tight_k A boolean flag indicating if the difference D = y - x constructed so far using bits > `bit` exactly matches the prefix of K.
* If true, the current bit difference d_bit cannot exceed K's bit K_current_bit at position `bit`.
* If false, D is already strictly less than K's prefix, so any d_bit (0 or 1) is permissible with respect to the K constraint.
* @param current_borrow A boolean flag indicating if a borrow is required *into* the current bit position `bit` from the next higher bit position `bit + 1`
* due to the subtraction y - x calculation at lower bit positions (bits < `bit`).
* Effectively, this is the borrow generated from processing bit `bit-1`.
* @return The number of ways to assign bits for x and y from position `bit` down to 0, such that all conditions are met.
*/
long long solve(int bit, bool tight_k, bool current_borrow) {
// Base case: If all bit positions (59 down to 0) have been processed.
if (bit < 0) {
// A valid pair (x, y) satisfying x <= y is found if and only if the final borrow state is 0.
// A final borrow state of 1 would imply that the overall subtraction y - x resulted in a negative value (y < x), violating the condition x <= y.
return current_borrow == 0 ? 1 : 0;
}
// Create a tuple representing the current DP state for memoization lookup.
tuple<int, bool, bool> state = {bit, tight_k, current_borrow};
// Check if the result for this state has already been computed and stored in the memoization table.
// Using find() is slightly more efficient than count() followed by operator[] access.
auto it = memo.find(state);
if (it != memo.end()) {
return it->second; // Return the cached result.
}
long long count_for_state = 0; // Initialize the count for the current state.
// Extract the bits of N (N_param) and K (K_param) at the current bit position `bit`.
long long N_current_bit = (N_param >> bit) & 1;
long long K_current_bit = (K_param >> bit) & 1;
// Iterate through all possible combinations of bit values for x and y at the current position `bit` (0 or 1).
for (int x_bit = 0; x_bit <= 1; ++x_bit) {
for (int y_bit = 0; y_bit <= 1; ++y_bit) {
// Check the primary bitwise condition: (x_bit AND y_bit) must equal N_current_bit.
if (((x_bit & y_bit) & 1) != N_current_bit) {
continue; // If this condition fails, this combination of (x_bit, y_bit) is invalid for this state. Skip to the next iteration.
}
// Calculate the effective difference at the current bit for the subtraction y - x.
// This calculation incorporates the borrow (`current_borrow`) from the lower bit's subtraction.
// `diff` represents y_bit - x_bit - current_borrow. It can range from -2 (0-1-1) to 1 (1-0-0).
int diff = y_bit - x_bit - current_borrow;
// Calculate the current bit (`d_bit`) of the total difference D = y - x.
// This is essentially `diff mod 2`. The expression `(diff % 2 + 2) % 2` handles potential negative results of `diff` correctly to produce 0 or 1.
int d_bit = (diff % 2 + 2) % 2;
// Determine the borrow (`next_borrow_val`) needed for the next higher bit position (`bit + 1`).
// This borrow value will be passed down recursively as `current_borrow` when calling `solve` for `bit - 1`.
// A borrow is generated if `diff` is negative.
bool next_borrow_val = (diff < 0);
// Check the constraint D <= K using the tightness flag `tight_k`.
// Assume the tightness constraint might continue (`next_tight_k = tight_k`).
bool next_tight_k = tight_k;
if (tight_k) {
// If the constraint D <= K is currently tight (i.e., the prefix of D matches K's prefix):
// The current difference bit `d_bit` cannot exceed K's current bit `K_current_bit`.
if (d_bit > K_current_bit) {
continue; // This path is invalid because it would make D > K. Skip to the next iteration.
}
// If `d_bit` is strictly less than `K_current_bit`, the constraint D <= K is now strictly satisfied.
// The tightness is broken for all subsequent lower bits.
if (d_bit < K_current_bit) {
next_tight_k = false;
}
// If `d_bit == K_current_bit`, the tightness continues, and the check must proceed for lower bits.
}
// If all conditions are met for the current bit assignment (x_bit, y_bit):
// Recursively call the `solve` function for the next lower bit position (`bit - 1`).
// Pass the updated tightness flag (`next_tight_k`) and the calculated borrow (`next_borrow_val`).
// Add the result returned by the recursive call to the total count for the current state.
count_for_state += solve(bit - 1, next_tight_k, next_borrow_val);
}
}
// Store the computed count for the current state `state` in the memoization table before returning.
return memo[state] = count_for_state;
}
int main() {
// Optimize standard input/output operations for faster execution.
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// Read the input values for N and K.
cin >> N_param >> K_param;
// Handle the special case where N = 0.
if (N_param == 0) {
if (K_param == 0) {
// If N=0 and K=0, the only pair satisfying all conditions (x AND y = 0, 0 <= x <= y, y - x <= 0) is (0, 0).
cout << 1 << endl;
} else {
// If N=0 and K >= 1, there are infinitely many solutions.
// For example, pairs (2^k - 1, 2^k) for any k >= 1 satisfy:
// x AND y = (2^k - 1) AND 2^k = 0.
// 0 <= 2^k - 1 <= 2^k is true.
// y - x = 2^k - (2^k - 1) = 1. Since K >= 1, y - x <= K holds.
// As k can be arbitrarily large, there are infinite pairs.
cout << "INF" << endl;
}
return 0; // Program finished after handling the N=0 case.
}
// If N > 0, it can be shown that the number of solutions (x, y) is finite.
// Use the Digit DP approach implemented in the `solve` function.
// Start the recursion from a sufficiently high bit position. Bit 59 is safe as it covers numbers up to 2^60 - 1,
// which is far beyond the potential range required by N <= 10^5 and K <= 300.
// The initial call state is:
// bit = 59 (most significant bit considered)
// tight_k = true (initially, the difference D must be <= K, so the constraint is tight)
// current_borrow = 0 (there is no borrow into the most significant bit calculation)
cout << solve(59, true, 0) << endl;
return 0;
}