HDU 5976 Detachment 【贪心】 (2016ACM/ICPC亚洲区大连站)-白红宇

HDU 5976 Detachment 【贪心】 (2016ACM/ICPC亚洲区大连站)

阅读量：5018 次

发布时间：2019-06-12

本文共 3143 字，大约阅读时间需要 10 分钟。

Detachment

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 570    Accepted Submission(s): 192

Problem Description

In a highly developed alien society, the habitats are almost infinite dimensional space.

In the history of this planet,there is an old puzzle.

You have a line segment with x units’ length representing one dimension.The line segment can be split into a number of small line segments:

Input

The first line is an integer T,meaning the number of test cases.

Then T lines follow. Each line contains one integer x.

1≤T≤10^6, 1≤x≤10^9

Output

Maximum s you can get modulo 10^9+7. Note that we wants to be greatest product before modulo 10^9+7.

Sample Input

1 4

Sample Output

4

Source

Recommend

wange2014   |   We have carefully selected several similar problems for you:

| | |

题目链接：

题目大意：

　　给一个数N(N<=10⁹)，让你把它拆成若干各不相同的数Ai，ΣAi=N，要求ΠAi（累乘）最大。

题目思路：

　　【贪心】

　　首先肯定要把位数拆的尽量多，手写了20以内的拆法。

　　发现以2为首相的递增序列累乘最大，所以我的想法就是把N拆成2+3+...+x<=n，

　　先找到x，之后算一下n还多了多少，就把后面依次+1，变成2+3+...+y+(y+2)+(y+3)+...+(x+1)。

　　这时候它们的累乘是最大的。

　　（特殊情况是从2到x都加1之后还剩余1，这时候把最后一项再加1，变成3+4+...+x+(x+2)

1 //  2 //by coolxxx  3 /*  4 #include
      
         5 #include
       
          6 #include
        
           7 #include
         
            8 #include
            9 #include
           
             10 #include
            
              11 #include
             
               12 #include
              
                13 #include
               
                 14 #include
                
                  15 #include
                 
                   16 #include
                  
                    17 #include
                   
                     18 #include
                    
                      19 //#include
                     
                       20 #define min(a,b) ((a)<(b)?(a):(b)) 21 #define max(a,b) ((a)>(b)?(a):(b)) 22 #define swap(a,b) ((a)^=(b),(b)^=(a),(a)^=(b)) 23 */ 24 #include
                      
                        25 #pragma comment(linker,"/STACK:1024000000,1024000000") 26 #define abs(a) ((a)>0?(a):(-(a))) 27 #define lowbit(a) (a&(-a)) 28 #define sqr(a) ((a)*(a)) 29 #define mem(a,b) memset(a,b,sizeof(a)) 30 #define eps (1e-8) 31 #define J 10000 32 #define mod 1000000007 33 #define MAX 0x7f7f7f7f 34 #define PI 3.14159265358979323 35 #define N 45004 36 using namespace std; 37 typedef long long LL; 38 double anss; 39 LL aans; 40 int cas,cass; 41 int n,m,lll,ans; 42 LL a[N],ni[N]; 43 LL mi(LL x,LL y) 44 { 45 LL z=1; 46 while(y) 47 { 48 if(y&1)z=(z*x)%mod; 49 x=(x*x)%mod; 50 y>>=1; 51 } 52 return z; 53 } 54 void init() 55 { 56 int i; 57 a[1]=1; 58 ni[1]=1; 59 for(i=2;i
                       
                        >1; 91 if(mid*mid+mid<=m)l=mid; 92 else r=mid-1; 93 } 94 m-=l*l+l; 95 m/=2; 96 if(m==l) 97 { 98 aans=a[l]*(l+2)%mod*mi(2,mod-2)%mod; 99 }100 else101 {102 x=l+1-m;103 aans=a[l+1]*mi(x,mod-2)%mod;104 }105 printf("%lld\n",aans);106 }107 return 0;108 }109 /*110 //111 112 //113 */