原题传送门：mit
前言
这道题是今天模拟赛T1，赛时只有 \(60\) 分。还有一位巨佬这道题保龄了。
题意
给定一个正整数 \(n\)，将 \(n\) 拆分成 \(k\) 个数之和。（\(k\) 为任意正整数）
求：\(k\) 个数的乘积最大是多少？乘积的期望是多少？
思路
首先看第一个问题。易证，要让乘积最大，必须将 \(n\) 分成若干个 \(3\)。当然如果最后剩了 \(1\) 的话就换成两个 \(2\)。
再看第二个问题，赛时想了好久都没有想出来。首先我们可以想到 \(O(n^{2})\) 的 \(dp\)。
设 \(f_{i}\) 表示正整数为 \(i\) 的时候的期望。假设当前这个数拆成了 \(k\)，则有：
\(f_{i}=\frac{1}{i} \times \sum_{k=1}^{i} f[i-k]\)
然后考虑如何优化。可以发现式子后面的 \(\sum_{k=1}^{i} f[i-k]\) 可以用前缀和优化。
于是设 \(h_{i} = \sum_{k = 1}^{i}f_{k}\)，设 \(g_{i}=\sum_{k=1}^{i}f_{k} \times(i-k+1)\)，则有：
\(f_{i}=g_{i-1} \times \frac{1}{i}\)
\(h_{i}=h_{i-1} +f_{i}\)
\(g_{i}=g_{i-1}+h_{i}\)
这样就可以 \(O(n)\) 算出答案了，答案就是 \(f_{n}\)。除以 \(i\) 的时候改为乘上 \(i\) 的逆元就行了。
Code
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define inf 0x3f3f3f3f
#define ls id << 1
#define rs id << 1 | 1
#define re register
typedef pair <int,int> pii;
const int MAXN = 5e5 + 10;
const int MAXM = 20;
int m,n,inv[MAXN],MAX = 1,mod;
int f[MAXN],g[MAXN],h[MAXN];
signed main()
{
cin >> n >> mod;m = n;
while(m >= 5){MAX = MAX * 3 % mod;m -= 3;}
MAX = MAX * m % mod;
inv[0] = inv[1] = 1;
for(int i = 2;i <= n;i++) inv[i] = inv[mod % i] * (mod - mod / i) % mod;
f[0] = g[0] = h[0] = 1;
for(int i = 1;i <= n;i++)
{
f[i] = g[i - 1] * inv[i] % mod;
h[i] = (h[i - 1] + f[i]) % mod;
g[i] = (g[i - 1] + h[i]) % mod;
}
cout << MAX << endl << f[n];
return 0;
}