主题：第57次编程比赛题目
iAkiak [专家分：8460] 发布于 2007-07-13 18:05:00
整数分划可能不少人都做过了，把一个正整数拆分为若干个正整数的和，问有多少种不同的拆法。比如对正整数4，
4=1+1+1+1
4=2+1+1
4=2+2
4=3+1
4=4
共有5种。现在问，如果拆成2的幂的和，有多少种不同的拆法
比如对正整数4，
4=1+1+1+1
4=2+1+1
4=2+2
4=4
共有4种。
请给出对任意正整数n(0<n<2000000)，拆分为2的幂之和的拆分方法数。输出这个数字模1000000的值。
接口定义：
[code]
namespace ID // 你的名字
{
int bp(int n); // 求解函数，测试过程可能多次调用
void init(); // 初始化，测试开始时调用一次
void release(); // 清理，测试结束时调用一次
}
[/code]
注意，测试过程形如：
[code]
t1 = time();
ID::init();
for (i = 0; i < testCase; i++)
ans[i] = ID::bp(data[i]);
ID::release();
t2 = time();
check(ans);
[/code]
也就是说init,release的时间也算到统计时间内。
回复列表 （共8个回复）
沙发
逆行行 [专家分：30] 发布于 2007-07-14 13:14:00
我对c++不熟........看来不能用纯c了
新人看不懂.........门槛高
板凳
小黑骑DK [专家分：610] 发布于 2007-07-14 13:46:00
namespace DK // ÄãµÄÃû×Ö
{
const int MAX = 2000000;
const int MOD = 1000000;
int *p = NULL;
int bp(int n); // Çó½âº¯Êý£¬²âÊÔ¹ý³Ì¿ÉÄܶà´Îµ÷ÓÃ
void init(); // ³õʼ»¯£¬²âÊÔ¿ªÊ¼Ê±µ÷ÓÃÒ»´Î
void release(); // ÇåÀí£¬²âÊÔ½áÊøʱµ÷ÓÃÒ»´Î
}
void DK::init(void)
{
int i;
p = new int[MOD*32];
for (i=0; i<MOD; i++)
{
p[i*32] = 1;
}
}
int DK::bp(int n)
{
int bit = 1;
int num = n;
int r,c,rSub,cSub;
int result = 0;
//Çó³ö×î´óλÊý
while ((num/=2) != 0)
{
bit++;
}
n /= 2;//żÊýnÓën+1µÄ·Ö¸î·½·¨ÊÇÒ»ÑùµÄ
for (c=1; c<bit; c++)
{
num = 1<<c;
for (r=1; (2*r+1)<num; r++);
for (; r<=n; r++)
{
rSub = 2*r+1 - num;//·Ö¸îÊý°üº¬numʱ
cSub = c + 1;
if (rSub < num)
{
for (cSub=1; (rSub>>cSub) != 0; cSub++);
}
rSub /= 2;
result = p[r*32 + c-1] + p[rSub*32 + cSub-1];
if (result >= MOD)
{
p[r*32+c] = result % MOD;
}
else
{
p[r*32+c] = result;
}
}
}
return p[n*32 + bit-1];
}
void DK::release(void)
{
delete [] p;
}
//求模太费时间了，但是又想不出好的方法
3 楼
isjk [专家分：210] 发布于 2007-07-14 16:53:00
namespace isjk
{
int bp(int n)
{
if(n&0x1)
{
n-=1;
n = n % 1000000;
return n;
}
else
{
n = n % 1000000;
return n;
}
}
void init();{}
void release();{}
}
4 楼
crossbow [专家分：150] 发布于 2007-07-14 17:27:00
namespace crossbow
{
// Sumsets, USACO 2005 January Silver
static int table[1000001];
void init(void)
{
table[0] = 1;
for (int i = 0; i <= 1000000; ++i)
if ((table[i] = table[i - 1] + table[i / 2]) >= 1000000)
table[i] -= 1000000;
}
int bp(int n)
{
return table[n / 2];
}
void release(void)
{
;
}
}
5 楼
dielsalder [专家分：2330] 发布于 2007-07-14 21:01:00
[url]http://acm.pku.edu.cn/JudgeOnline/problem?id=2229[/url]
[url]http://www.blog.edu.cn/user4/ericlee211/archives/2007/1659356.shtml[/url]
[url]http://cache.baidu.com/c?word=sumsets&url=http%3A//blog%2Ecsdn%2Enet/c0053/articles/770114%2Easpx&p=877cc01391904eaf5efcc471094e&user=baidu#baidusnap0[/url]
6 楼
knate [专家分：570] 发布于 2007-07-15 15:11:00
看看，看似不是很容易的啊！！
有一个思路，！
设 2^(n)<＝x<=2^(n+1）
递归求解当2的最大幂2^n，2^(n-1)。。。。2，1时的可能！
7 楼
Twent [专家分：30] 发布于 2007-07-15 19:42:00
呃不会做- - 随便写了个算法 - -Dev c++
#include <iostream>
using namespace std;
namespace twent{
long f[2000001];
long tp[30];
long tpn;
void init(){
long t,i,j;
memset(tp,0,sizeof(tp));
tp[0]=1;
for (int i=1;tp[i-1]<=2000000;i++) {
tp[i]=tp[i-1]*2;
tpn++;
// cout<<tpn<<" "<<tp[i]<<endl;
}
memset(f,0,sizeof(f));
f[0]=1;
for (i=0;i<=tpn;i++){
for (j=tp[i];j<=2000000;j++){
t=f[j]+f[j-tp[i]];
f[j]=t>1000000?t%1000000:t;
}
}
}
long bp(long n){
return f[n];
}
void release(){
}
}
8 楼
iAkiak [专家分：8460] 发布于 2007-07-15 23:55:00
时间到。貌似这次人不多:(
我来回复
您所在位置：