結果
問題 |
No.822 Bitwise AND
|
ユーザー |
![]() |
提出日時 | 2019-04-27 17:14:20 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 16 ms / 2,000 ms |
コード長 | 1,167 bytes |
コンパイル時間 | 1,606 ms |
コンパイル使用メモリ | 168,420 KB |
実行使用メモリ | 39,344 KB |
最終ジャッジ日時 | 2024-06-25 18:17:22 |
合計ジャッジ時間 | 2,517 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 17 |
ソースコード
#include <bits/stdc++.h> #define fst(t) std::get<0>(t) #define snd(t) std::get<1>(t) #define thd(t) std::get<2>(t) #define unless(p) if(!(p)) #define until(p) while(!(p)) using ll = std::int64_t; using P = std::tuple<int,int>; constexpr ll B = 135000, INF = std::numeric_limits<ll>::max() / 2; int N, K; ll dp[17][270000]; ll add(ll x, ll y){ if(x < INF && y < INF){ return x + y; } return INF; } ll rec(int i, int d){ if(i == 17){ d -= B; if(0 <= d && d <= K){ return 1; }else if(d <= - (1 << 17) + K){ return INF; } return 0; } if(dp[i][d] != -1){ return dp[i][d]; } ll res; if(N >> i & 1){ res = rec(i + 1, d); }else{ res = add(add(rec(i + 1, d + (1 << i)), rec(i + 1, d - (1 << i))), rec(i + 1, d)); } return dp[i][d] = res; } int main(){ std::cin.tie(nullptr); std::ios::sync_with_stdio(false); std::cin >> N >> K; memset(dp, -1, sizeof(dp)); ll res = rec(0, B); if(res < INF){ std::cout << res << std::endl; }else{ std::cout << "INF" << std::endl; } }