首页 / 软件开发 / 数据结构与算法 / UVa 12208 How Many Ones Needed？ （组合数学）

UVa 12208 How Many Ones Needed？ （组合数学）2014-07-25

12208 - How Many Ones Needed？

Time limit: 3.000 seconds

http://uva.onlinejudge.org/index.php？option=onlinejudge&Itemid=99999999&category=244&page=show_problem&problem=3360

水。

完整代码：

/*0.035s*/#include<bits/stdc++.h>using namespace std;typedef long long ll;ll c[31][31], sum;int i, j, cnt;void init（）{for （i = 0; i < 31; ++i）c[i][0] = c[i][i] = 1;for （i = 2; i < 31; ++i）for （j = 1; j < i; ++j）c[i][j] = c[i - 1][j - 1] + c[i - 1][j];}inline ll calc（int n, bool yeah）{sum = cnt = 0;for （i = 31; i >= 0; --i）{if （n & （1 << i））{for （j = 0; j <= i; ++j）sum += c[i][j] * （j + cnt）;++cnt;}}if （yeah） sum += cnt;///把数n也算上return sum;}int main（）{init（）;int a, b, cas = 0;ll ans;while （scanf（"%d%d", &a, &b）, a || b）printf（"Case %d: %lld
", ++cas, calc（b, true） - calc（a, false））;return 0;}

作者：csdn博客 synapse7