首页 > 其他 > 详细

4.13 | 学习笔记

时间:2019-04-13 23:36:44      阅读:143      评论:0      收藏:0      [点我收藏+]

1.整数拆分为2 的幂的和

技术分享图片

 

用数组a[ ]直接记录结果。

从前往后推的时候,有两种可能性,分为a[ 2m+1] 和a[ 2m ];

易知a[ 2m+1 ]=a[ 2m ];

对于a[ 2m ]它的所有拆分方式分为两大类:

1)含有1的,这部分所有方式都去掉1,就得到a[ 2m-1 ]

2)不含有1的,也就是分出的都是2的倍数,那么都除以2,就得到a [m ]

附上AC代码:

#include<bits/stdc++.h>
using namespace std;
long long int a[1000001]={0,1,2};
long long int t,n;
int main()
{
  for(int i=3;i<1000001;i++)
  {
    if(i%2)a[i]=a[i-1];
    else a[i]=(a[i-2]+a[i/2])%1000000000;
  }
  cin>>t;
  for(int i=0;i<t;i++)
  {
    cin>>n;
    cout<<"case #"<<i<<":\n"<<a[n]<<endl;
  }
  return 0;
}

  

4.13 | 学习笔记

原文:https://www.cnblogs.com/MissCold/p/10703382.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!