結果

問題 No.822 Bitwise AND
コンテスト
ユーザー yuppe19 😺
提出日時 2019-04-28 15:02:22
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 2,255 bytes
コンパイル時間 1,178 ms
コンパイル使用メモリ 91,104 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-06-25 18:17:18
合計ジャッジ時間 1,831 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bitset>
#include <iostream>
#include <vector>
using namespace std;
using i64 = int64_t;

constexpr i64 inf = 987'654'321'987'654'321LL;

string to_bin(const i64 a) {
  return bitset<40>(a).to_string();
}

int cmp(int x, int y) {
  if(x <  y) { return 0; }
  if(x == y) { return 1; }
  return 2;
}

int next_state(int a, int b, int cur) {
  int res = cmp(a, b);
  if(res == 1) { res = cur; }
  return res;
}

// 0 <= x <= y
// y - x <= K  (y <= x + K)
// x & y = N
i64 f(int N, int K) {
  if(N < K) { return inf; }
  string s = to_bin(N);
  string t = to_bin(K);
  int n = static_cast<int>(s.size());
  // dp[xはyより未満/丁度/超過][yはx+Kより未満/丁度/超過][x+Kで繰り上がったか][x&yはNより未満/丁度/超過] := パターン数
  vector<vector<vector<vector<i64>>>> dp(3, vector<vector<vector<i64>>>(3, vector<vector<i64>>(2, vector<i64>(3, 0)))); // dp[3][3][2][3]
  dp[1][1][0][1] = 1;
  for(int i=n-1; i>=0; --i) {
    vector<vector<vector<vector<i64>>>> ndp(3, vector<vector<vector<i64>>>(3, vector<vector<i64>>(2, vector<i64>(3, 0))));
    for(int state1=0; state1<3; ++state1) {
      for(int state2=0; state2<3; ++state2) {
        for(int state3=0; state3<3; ++state3) {
          for(int carry=0; carry<2; ++carry) {
            if(!dp[state1][state2][carry][state3]) { continue; }
            for(int xi=0; xi<2; ++xi) {
              for(int yi=0; yi<2; ++yi) {
                int val    = (carry + xi + t[i] - '0') % 2,
                    ncarry = (carry + xi + t[i] - '0') / 2,
                    nstate1 = next_state(xi,      yi,         state1),
                    nstate2 = next_state(yi,      val,        state2),
                    nstate3 = next_state(xi & yi, s[i] - '0', state3);
                ndp[nstate1][nstate2][ncarry][nstate3] += dp[state1][state2][carry][state3];
              }
            }
          }
        }
      }
    }
    dp = ndp;
  }
  i64 res = 0;
  for(int state1=0; state1<2; ++state1) {
    for(int state2=0; state2<2; ++state2) {
      res += dp[state1][state2][0][1];
    }
  }
  return res;
}

int main(void) {
  int N, K; scanf("%d%d", &N, &K);
  i64 res = f(N, K);
  if(res == inf) {
    puts("INF");
  } else {
    printf("%ld\n", res);
  }
  return 0;
}
0