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