[ 等待填坑中]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 |
// // URAL 1057.cpp // playground // // Created by Adam Chang on 2015/08/03. // Copyright © 2015年 Adam Chang. All rights reserved. // #include <iostream> #include <algorithm> #include <queue> #include <vector> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <ctime> #include <iomanip> #include <cmath> #include <set> #include <stack> #include <cmath> #include <map> #include <bitset> using namespace std; unsigned int x = 0, y = 0, k = 0, b = 0; unsigned int dp[33][33];//dp[depth][request numbers of 1] void get_dp(){ memset(dp, 0, sizeof(dp)); dp[0][0] = 1; dp[1][0] = 1; dp[1][1] = 1; for (int i = 2; i <= 32; i++) { dp[i][0] = 1; for (int j = 1; j <= 32; j++) { dp[i][j] = dp[i-1][j-1] + dp[i-1][j]; } } } unsigned int get_ans(unsigned int a){ unsigned int ret = 0; int hav = 0; for (int i = 31; i >= 0; i--) { if (a & (1 << i)) { if (k >= hav) { ret += dp[i][k-hav]; } hav++; } } return ret; } bitset<32> b_to_bin(unsigned int n){ vector<int> vec; while (n) { vec.push_back(n % b); n /= b; } bitset<32> bit; for (int i = 1; i <= vec.size(); i++) { if (vec[(int)vec.size() - i] == 1) { bit[(int)vec.size() - i] = 1; }else if(vec[(int)vec.size() - i] == 0){ bit[(int)vec.size() - i] = 0; }else { for (int j = (int)vec.size() - i; j >= 0; j--) { bit[j] = 1; } break; } } return bit; } int main(){ cin >> x >> y >> k >> b; get_dp(); bitset<32> bitx(b_to_bin(x)); bitset<32> bity(b_to_bin(y)); cout << get_ans(bity.to_ulong()+1) - get_ans(bitx.to_ulong()) << endl; return 0; } |