Fork me on GitHub

逆元+前缀积+STL二分

发表于 | 分类于 | 热度 ℃  |  
字数统计 526 字 | 阅读时长 2 分钟

这题做了挺久了，考察的东西还挺多，而且还是一道思维题。

原题链接：HDU - 5976

华师男和他女票又创造了一个新的游戏
他们一起想一个数x，然后对这个进行拆分成任意多个 各不相同的数， a1,a2,a3 … 满足(x= a1+a2+a3+…) 他们决定齐心协力找到一种拆分方法，使得所有这些数的乘积最大。

Input

第一行有一个整数T，表示有T组测试数据。
随后T行，每行都有一个数字x。
1≤T≤10^6, 1≤x≤10^9

Output

先获取乘积的最大值，再对其模10^9+7后输出。

Sample Input

2
4
5

Sample Output

4
6

Hint

4 = 4
5 = 2 + 3，2*3 = 6

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include<bits/stdc++.h>
using namespace std;
const int mod=1000000007;
typedef long long ll;
ll num[100005],top=1,ans[100005],ni[100005];
void init()
{
    num[top]=1;
    ans[top]=1;
    ni[top]=1;
    ll i,now=0,mul=1;
    for(i=2; now<=1000000000; i++)
    {
        now+=i;
        num[++top]=now; //前缀和
        mul=mul*i%mod;
        ans[top]=mul; //前缀积
        ni[i]=(mod-mod/i)*ni[mod%i]%mod; //逆元
    }
}
int main()
{
    init();
    ll t;
    scanf("%lld",&t);
    while(t--)
    {
        ll x;
        scanf("%lld",&x);
        ll s=lower_bound(num+1,num+1+top,x)-num;
        if(num[s]==x)
        {
            printf("%lld\n",ans[s]);
        }
        else
        {
            s--;
            ll need=x-num[s],re=ans[s];
            if(need==s)
            {
                re=re*ni[2]%mod;
                re=re*(s+2)%mod;
            }
            else
            {
                re=re*ni[s+1-need]%mod;
                re=re*(s+1)%mod;
            }
            printf("%lld\n",re);
        }
    }
    return 0;
}

尽量将X拆成2+3+4……+k，如果x恰好能拆成，则答案就是k！如果x拆完还剩t，则将X拆为2+3+……+(k-t) + (k–t+2)+(k–t+3)+……+k+(k+1);通过预处理可以得出(k+1)!只需乘上（k – t + 1）的逆元。

此外有个特例，如果减到最后剩下的数和最后一个数一样大，多出来的一就加在最后一个数上面。

PS：原来一般的数组也可以用STL二分。。。

附上逆元的公式 (要求MOD为素数):

1
2
3
4
int[] inv = new int[MAXN];  
inv[1] = 1;  
for (int i = 2; i<MAXN; i++)  
    inv[i] = inv[MOD%i]*(MOD-MOD/i)%MOD;

更多关于逆元的知识: http://blog.csdn.net/xwxcy/article/details/51493193

donate the author