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

GreenCloudS

 
 
 

日志

 
 

BZOJ-1025: [SCOI2009]游戏(背包)  

2014-04-24 17:57:00|  分类: oi,bzoj,DP |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

题目:http://www.lydsy.com/JudgeOnline/problem.php?id=1025


题目很明显求sigma(ai)=n,lcm(a1,a2...,an)=m,m的个数,然后就可以证出一个神奇的东西:存在m=p1^a1 * p2^a2 .. pq^aq,等价于sigma(pi^ai)<=n(http://blog.163.com/benz_/blog/static/18684203020115131147522/),然后DP即可。


代码:

  • #include <cstdio>

  • #include <algorithm>

  • #include <cstring>

  •  

  • using namespace std ;

  •  

  • const int maxn =1010;

  •  

  • int p[ maxn ], pcnt =0, n ;

  • bool f[ maxn ];

  •  

  • void INIT(  ){

  •     memset( f ,true,sizeof( f ));

  •     for(int i =2; i <= n ;++ i )if( f[ i ]){

  •         p[++ pcnt ]= i ;

  •         for(int j = i <<1; j <= n ; j += i ) f[ j ]=false;

  •     }

  • }

  •  

  • typedef long long ll ;

  •  

  • ll dp[ maxn ][ maxn ];

  •  

  • int main(  ){

  •     scanf("%d",&n );

  •     INIT(  );

  •     memset( dp ,0,sizeof( dp ));

  •     dp[0][0]=1;

  •     for(int i =0; i ++< pcnt ;){

  •         for(int j =0; j <= n ;++ j ) dp[ i ][ j ]= dp[ i -1][ j ];

  •         for(int k = p[ i ]; k <= n ; k *= p[ i ]){

  •             for(int j = k ; j <= n ;++ j ) dp[ i ][ j ]+= dp[ i -1][ j - k ];

  •         }

  •     }

  •     ll ans =0;

  •     for(int i =0; i <= n ;++ i ) ans += dp[ pcnt ][ i ];

  •     printf("%lld\n", ans );

  •     return 0;

  • }


  评论这张
 
阅读(3)| 评论(6)
推荐 转载

历史上的今天

评论

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

页脚

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