几题

1

给定质数 $p$ 和询问次数 $T$，对于每个询问求：

$$\left ( \prod_{i=1}^{n-1} (a+id)\right ) \mod p$$

$1\le T \le 10^6,0\le a,b< p \le 10^7, 1\le n\le 10^9$。

这么傻逼的题我居然没想出来我他妈是什么品种的玛卡巴卡

$$\begin{matrix} \left ( \prod_{i=1}^{n-1} (a+id)\right ) \mod p \\ \left ( \prod_{i=1}^{n-1} d(\frac{a}{d}+i)\right ) \mod p \\ \left ( d^n\prod_{i=1}^{n-1} (\frac{a}{d}+i)\right ) \mod p \\ \end{matrix}$$

$p$ 只有 $10^7$，预处理阶乘即可。

2

$$f_{i,j}=\min_{k<i}\left\{f_{k,j-1}+(i-k-1)a_k+a_i\right\}$$

第一次写斜率优化，进行一个念的纪。

考场上由于我推出来的柿子比较不优美加上斜率优化不熟并没有做出来。

$$\begin{matrix} f_{i,j}=\min_{k<i}\left\{f_{k,j-1}+(i-k-1)a_k+a_i\right\} \\ f_{i,j}-a_i=\min_{k<i}\left\{f_{k,j-1}+(i-k-1)a_k\right\} \\ f_{i,j}-a_i=\min_{k<i}\left\{f_{k,j-1}+(k+1)a_k+ia_k\right\} \\ \end{matrix}$$

令 $h_i=f_{i,j}-a_i$，$g_k=f_{k,j-1}+(k+1)a_k$：

$$h_i=\min_{j<i}\left\{g_j+ia_j\right\}$$

这个柿子就比较标准了。

考虑一个决策点 $k<j$ 什么时候比 $j$ 劣：

$$\begin{matrix} g_j+ia_j<g_k+ia_k\\ g_j-g_k<i(a_k-a_j)\\ \frac{g_j-g_k}{a_k-a_j}>i \end{matrix}$$

令 $y_i=g_i,x_i=-a_i$，那么 $j$ 优比前面决策都优的条件就是 $j$ 在二维平面与面前任意一个点构成直线的斜率要大于 $i$。同理，比后面优就是小于 $i$。

然后我们发现决策点一定在下凸壳上（注意 $x$ 坐标为负，也就是前面的点在右边，后面的在左边）。

然后又发现加决策点时在凸壳左边加，最有决策是从左到右第一个斜率大于 $i$ 的，用栈维护一下就行了。

维护下凸壳的时候是在左边加，所以是斜率小于当前斜率就弹出。

注意还要考虑 $a_j=a_k$ 的情况。

#include <bits/stdc++.h>
using namespace std;
#define int long long

inline int read() {
	int x = 0, f = 0; char c = 0;
	while (!isdigit(c)) f |= c == '-', c = getchar();
	while (isdigit(c)) x = x * 10 + (c & 15), c = getchar();
	return f ? -x : x;
}

#define N 2005
int n, m, a[N], f[N][N], g[N], h[N], st[N];

signed main() {
	freopen("contest.in", "r", stdin);
	freopen("contest.out", "w", stdout);
	for (int T = read(); T --;) {
		n = read(), m = read();
		for (int i = 1; i <= n; i ++) {
			a[i] = read();
		}
		sort(a + 1, a + n + 1);
		for (int i = 1; i <= n; i ++) f[i][1] = a[i];
		for (int j = 2; j <= m; j ++) {
			for (int i = 1; i <= n; i ++) {
				g[i] = f[i][j - 1] - (i + 1) * a[i];
			}
			h[1] = 1e9;
			int cnt = 0;
			auto K = [&](int k, int j) -> long double {
				if (a[j] == a[k]) return 1e17;
				return 1. * (g[j] - g[k]) / (a[k] - a[j]);
			};
			for (int i = 2; i <= n; i ++) {
				while (cnt > 1 && K(st[cnt], i - 1) >= K(st[cnt - 1], st[cnt])) cnt --;
				st[++ cnt] = i - 1;
				while (cnt > 1 && K(st[cnt - 1], st[cnt]) <= 1. * i) cnt --;
				h[i] = g[st[cnt]] + i * a[st[cnt]];
			}
			for (int i = 1; i <= n; i ++) f[i][j] = h[i] + a[i];
		}
		int res = 1e17;
		for (int i = 1; i <= n; i ++) {
			res = min(res, f[i][m] + (n - i) * a[i]);
		}
		printf("%lld\n", res);
	}
	return 0;
}
/*
		for (int i = 2; i <= n; i ++) { f[i][1] = a[i];
			for (int j = 1; j <= min(i, m); j ++) {
				for (int k = i - 1; k >= 1; k --) {
					f[i][j] = min(f[i][j], f[k][j - 1] + (i - k - 1) * a[k] + a[i]);
				}
			}
		}
*/

3

给定一棵树，你要对于每个 $i$ 求出有多少个 $n$ 的排列 $a$ 满足：

$$\sum_{j=1}^{n-1}[a_j \ is\ the\ grandfather\ of \ a_{j+1}] \ \ = i$$

$1\le n \le 5000$。

首先恰好转至少。

一个排列一定可以分成若干段，使得每一段都是由从祖先到儿子。

所以可以设 $f_{x,i}$ 表示考虑以 $x$ 为根的子树，分成 $i$ 个段，每个段都是由祖先到儿子的方案数（段没有先后顺序）。

首先考虑合并两个子树的 $f$，因为没有顺序直接方案数相乘即可。

$$f'_{x,i+j} \gets f_{x,i}\times f_{y,j}$$

然后要把 $x$ 放进去。因为 $x$ 是这个子树的根，所以它可以放到任一一段的开头或新开一个段，所以

$$f'_{x,i}=f_{x,i}\times i+f_{x,i-1}$$

然后考虑将其拼成一个完整的排列，设 $F_i$ 表示至少有 $i$ 个祖先到儿子位置的排列的位置。一个由 $n-i$ 个段拼起来的排列至少有 $i$ 个这样的位置，所以：

$$F_i=f_{1,n-i}\times (n-i)!$$

然后直接二项式反演。