刘源扳倒谷俊山内幕,燕子717新浪微博,主题班会活动
farmer john commanded his cows to search for different sets of numbers that sum to a given number. the cows use only numbers that are an integer power of 2. here are the possible sets of numbers that sum to 7:
1) 1+1+1+1+1+1+1
2) 1+1+1+1+1+2
3) 1+1+1+2+2
4) 1+1+1+4
5) 1+2+2+2
6) 1+2+4
help fj count all possible representations for a given integer n (1 <= n
<= 1,000,000).
input
a single line with a single integer, n.
output
the number of ways to represent n as the indicated sum. due to the potential huge size of this number, print only last 9 digits (in base 10 representation).
sample input
7
sample output
6
题意：整数n用2^n之和的形式表示的方案数
思路：当n>1时，若n为奇数，则每个分解方案中至少含有一个1项。此时若每种分解方案中去掉一个1项，方案数不发生改变。
即 n分解的方案数=（n-1）分解的方案数
若该n为偶数，则分为两类情况：
1、含有1项,同上，每个方案中去掉1项，方案数不变。
2、不含有1项，此时每个方案中最小项应为2，若将每一项除2，方案数不变。
即 n分解的方案数=（n-1）分解的方案数+（n/2）分解的方案数。
边界条件：当n=1时只有一种分解方案。
注意：可能溢出，需要取模
我要评论 1 #include<cstdio>
2 int s[1000005];
3 int main()
4 {
5 int n;
6
7 s[1]=1;
8 for( int i=2; i<=1000000; i++){
9 if( i%2==0 )
10 s[i]=(s[i-1]+s[i/2])%1000000000;
11 else
12 s[i]=s[i-1];
13 }
14 while(~scanf("%d",&n)){
15 printf("%d\n",s[n]);
16 }
17
18 return 0;
19 }
如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复
如何在没有core文件的情况下用dmesg+addr2line定位段错误
用QT制作3D点云显示器——QtDataVisualization
网友评论