http://acm.hdu.edu.cn/showproblem.php?pid=5976
题意: 给你一个数 n, 拆成不同的几份, 使乘积最大.
解法: 从 2 开始拆 2 , 3 , 4 ....l , 最后会余下 x , 0<=x <= l ;
再将 l 从后往前依次分配 1 给各元素.
- 1,x == l:3*4*5*...l * (l+2) = (csum[l] / 2) % mod * (l+2) (除以 2 要转为乘以 2 的逆元)
- 2,x == 0 : 2*3*...*l = csum[l]
- 3,x != 0 && x != l : 2 * 3 *...k * k+2*...l+1 = csum[l+1] / (index - c+ 1) (逆元求解)
- //#include <bits/stdc++.h>
- #include <cstdio>
- #include <cstring>
- #include <cmath>
- #include <algorithm>
- #include <iostream>
- #include <algorithm>
- #include <iostream>
- #include <cstdio>
- #include <string>
- #include <cstring>
- #include <stdio.h>
- #include <queue>
- #include <stack>
- #include <map>
- #include <set>
- #include <string.h>
- #include <vector>
- #define ME(x , y) memset(x , y , sizeof(x))
- #define SF(n) scanf("%d" , &n)
- #define rep(i , n) for(int i = 0 ; i <n ; i ++)
- #define INF 0x3f3f3f3f
- #define mod 1000000007
- using namespace std;
- typedef long long ll ;
- ll sum[100009];
- ll csum[100009];
- ll quickpow(ll a , ll b)
- {
- ll ans = 1 ;
- while(b)
- {
- if(b&1)
- {
- ans = ans * a % mod ;
- }
- b>>= 1 ;
- a = a * a % mod;
- }
- return ans ;
- }
- int main()
- {
- ll t ;
- scanf("%lld" , &t);
- for(int i = 2 ; i <= 100000 ; i++)
- {
- sum[i] += sum[i-1] + i ;
- }
- csum[1] = 1 ;
- for(int i = 2 ; i <= 100000 ; i++)
- {
- csum[i] = (csum[i-1] * i) % mod ;
- }
- while(t--)
- {
- ll n ;
- scanf("%lld" , &n);
- if(n <= 4)
- {
- printf("%lld\n" , n);
- continue ;
- }
- int index = upper_bound(sum , sum+100000 , n) - sum;
- index-- ;
- if(n - sum[index] == 0)
- {
- printf("%lld\n" , csum[index]);
- }
- else if(n - sum[index] == index)
- {
- printf("%lld\n" , csum[index] % mod * quickpow(2 , mod-2) % mod * (index + 2) % mod);
- }
- else
- {
- ll c = n - sum[index];
- printf("%lld\n" , csum[index] % mod * quickpow(index - c + 1 , mod - 2) % mod * (index+1) % mod);
- }
- }
- return 0 ;
- }
来源: http://www.bubuko.com/infodetail-3289699.html