注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fudq's AC Road

何以解忧,唯有AC!

 
 
 

日志

 
 

hdu 4651 Partition  

2013-08-07 14:50:07|  分类: ACM-hdu |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
http://acm.hdu.edu.cn/showproblem.php?pid=4651
题意:把数n拆成几个数(小于等于n)相加的形式,问有多少种拆法。
题解:Partition数列,打表出前几个数的结果发现是区分数数列。维基上有详细说明http://en.wikipedia.org/wiki/Partition_(number_theory)
p(k)=p(k-1)+p(k-2)-p(k-5)-p(k-7)+p(k-12)+p(k-15)-p(k-22)-p(k-26)+……
+(1, 2), -(5,7), +(12,15), -(22,26)……
1,5,12,22满足公式n*(3*n-1)/2。

/*
* fudq.cpp
*
* Created on: 2013-08-07
* Author: fudq
*/
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <stack>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <functional>
#include <numeric>
#include <cctype>
using namespace std;

#define FOR(i,a) for((i)=0;i<(a);(i)++)
#define MEM(a) (memset((a),0,sizeof(a)))
#define LL __int64

const int N=100010;
const int M=1000010;
const int MOD=1000000007ll;
const int INF=0x7fffffff;
const double eps=1e-7;
const double PI=acos(-1.0);

LL f[N];

void init()
{
f[0]=1;
for(LL i=1;i<=100000;i++)
{
f[i]=0;
for(LL j=1;;j++)
{
LL t,tt;
t=j*(3*j-1)/2;

if(t > i)
break;
tt=f[i-t];

if(t+j <= i)
tt=(tt+f[i-t-j])%MOD;

if(j&1)
f[i]=(f[i]+tt)%MOD;
else
f[i]=(f[i]-tt+MOD)%MOD;
}
}
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("testin.txt","r",stdin);
// freopen("testout.txt","w",stdout);
#endif
init();
int T,n;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
printf("%I64d\n",f[n]);
}
return 0;
}


  评论这张
 
阅读(158)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017