HDOJ 5646-DZY Loves Partition【数学】

骑猪看日落 2022-07-26 06:17 187阅读 0赞

# DZY Loves Partition #

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)

Total Submission(s): 1328 Accepted Submission(s): 501

Problem Description

DZY loves partitioning numbers. He wants to know whether it is possible to partition  n![Image 1][] into the sum of exactly  k![Image 1][] distinct positive integers.  
  
After some thinking he finds this problem is Too Simple. So he decides to maximize the product of these  k![Image 1][] numbers. Can you help him?  
  
The answer may be large. Please output it modulo  10![Image 1][]9![Image 1][]\+7![Image 1][].

Input

First line contains  t![Image 1][] denoting the number of testcases.  
  
 t![Image 1][] testcases follow. Each testcase contains two positive integers  n,k![Image 1][] in a line.  
  
(  1≤t≤50,2≤n,k≤10![Image 1][]9![Image 1][]![Image 1][])

Output

For each testcase, if such partition does not exist, please output  −1![Image 1][]. Otherwise output the maximum product mudulo  10![Image 1][]9![Image 1][]\+7![Image 1][].

Sample Input

4
    3 4
    3 2
    9 3
    666666 2

Sample Output

-1
    2
    24
    110888111
    
    
       
        
        
         
         
          Hint
        
         
    In 1st testcase, there is no valid partition.
    In 2nd testcase, the partition is $3=1+2$. Answer is $1\times 2 = 2$.
    In 3rd testcase, the partition is $9=2+3+4$. Answer is $2\times 3 \times 4 = 24$. Note that $9=3+3+3$ is not a valid partition, because it has repetition.
    In 4th testcase, the partition is $666666=333332+333334$. Answer is $333332\times 333334= 111110888888$. Remember to output it mudulo $10^9 + 7$, which is $110888111$.

解题思路：

n可以被分成k份，问被分成k份的这些数的乘积什么时候最大。

k\*(k+1)/2;

#include<stdio.h>
    #include<string.h>
    #include<algorithm>
    #include<math.h>
    #define mod 1000000007
    using namespace std;
    int main()
    {
    	int T;
    	scanf("%d",&T);
    	while(T--)
    	{
    		long long n,k,s;
    		s=1;
    		scanf("%lld%lld",&n,&k);
    		int i,j;
    		if(n<k*(k+1)/2)
    		{
    			printf("-1\n");
    			continue;
    		}
    		if(n%k==0)
    		{
    			int tem=n/k;
    			if(k&1)
    			{
    				s=tem;
    			} 
    			for(i=1;i<=k/2;i++)
    			{
    				s=s*(tem-i)*(tem+i)%mod;
    			}
    		}
    		else
    		{
    			int tem=k*(k-1)/2;
    			int num=(n-tem)%k;
    			int base=(n-tem)/k;
    			i=1;
    			for(;i<=num;i++)
    			{
    				s=s*(base+k-i+1)%mod;
    			}	
    			while(i<=k)
    			{
    				s=s*(base+k-i++)%mod;
    			}
    		}
    		printf("%lld\n",s);
    	}
    	return 0;
    }

[Image 1]: