| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
贴一个非DP的代码#include <cstdio>
using namespace std;
// C(N, >= K)
int nk(int N, int K) {
int re = 0;
for (int i = N, s; i >= K; --i) {
s = i == N ? 1 : s * (i + 1) / (N - i);
re += s;
}
return re;
}
// round number [0 - 2 ^ N)
int func(int N) {
int re = 1;
for (int i = 1; i <= N; ++i) {
re += nk(i - 1, (i >> 1) + (i & 1));
}
return re;
}
// round number [0, N)
int counts(int N) {
int re = 0;
// find highest bit
for (int i = 30, s1 = 0, s0 = 0; i >= 0; --i) {
if ((N >> i) & 1) {
if (++s1 == 1) {
re += func(i);
} else {
int t = s1 - s0 + i - 2;
re += nk(i, (t >> 1) + (t & 1));
}
} else if (s1 > 0) {
++s0;
}
}
return re;
}
int main(int argc, char **argv) {
int S, F;
scanf("%d%d", &S, &F);
printf("%d\n", counts(F + 1) - counts(S));
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator