題意：
給定一個區間，求區間內有多少個合法數（當這個數的二進制中0的個數>=1的個數稱為合法數 二進制無前導0）
思路：
cnt[i]表示二進制長度為i位（即最高位為1，其他位任意）時的合法數個數。
sum[i] 就是二進制長度<=i位的合法數個數。
然後從最高位枚舉到低位即可。維護當前0的個數。
#include#include #include #include #include template inline bool rd(T &ret) { char c; int sgn; if (c = getchar(), c == EOF) return 0; while (c != '-' && (c<'0' || c>'9')) c = getchar(); sgn = (c == '-') ? -1 : 1; ret = (c == '-') ? 0 : (c - '0'); while (c = getchar(), c >= '0'&&c <= '9') ret = ret * 10 + (c - '0'); ret *= sgn; return 1; } template inline void pt(T x) { if (x <0) { putchar('-'); x = -x; } if (x>9) pt(x / 10); putchar(x % 10 + '0'); } using namespace std; typedef long long ll; const int N = 100; int bit[N]; ll cnt[N], C[N][N], sum[N]; ll dfs(int len){ ll ans = sum[len - 1];//最高位（即len位一定是1）二進制長度<=len-1的合法數個數 int zero = bit[len]==0; for (int i(len-1); i; i--) { if (bit[i] == 0){ zero++; continue; } int tmp = zero + 1;//此時第i位可以填0也可以填1，若填0，則後面siz位可以任意填，填出來的數都不會大於x int siz = i - 1; if (tmp >= len - tmp)ans += 1LL << siz; else { for (int j = 0; j <= siz; j++)//同樣枚舉0的個數 if (tmp + j >= len - tmp - j) ans += C[siz][j]; } } ans += zero >= len - zero;//x這個數是不是合法 return ans; } ll solve(ll x){ if (x <= 1)return 1; int len = 0; for (ll tmp = x; tmp; tmp >>= 1)bit[++len] = tmp & 1; return dfs(len); } int main() { memset(C, 0, sizeof C);//計算組合數 C[1][0] = C[1][1] = 1; for (int i = 2; i < N; i++){ C[i][0] = 1; for (int j = 1; j < N; j++) C[i][j] = C[i - 1][j] + C[i - 1][j - 1]; } cnt[1] = 1; sum[1] = 1; for (int i = 2; i < N; i++){ cnt[i] = 0;//二進制長度為i，最高位是1，其他位任意時的合法數個數 for (int j = 0; j <= i - 1; j++) //因為最高位是1，所以自由位數有i-1個，枚舉其中0的個數j，若0的個數j>=1的個數i-j，則cnt[i]的方法數+=在i-1個位置中選j個0 if (j >= i - j) cnt[i] += C[i - 1][j]; sum[i] = cnt[i] + sum[i - 1]; } long long l, r; while (cin >> l >> r) cout << solve(r) - solve(l - 1) << endl; return 0; } /* 1 12 1 10 1 20 */
