20221207 - 模拟赛 | Final Fantasy = xixike = 人间忽晚，山河已秋

推式子 + 矩阵乘法，并查集启发式合并动态维护直径，单调性优化 dp

# A. 斐波那契

考场上只会 $k = 1$ 的部分分 /kk

本题大致思路是从 $k = 1$ 推到 $k = 2$ ，然后依次推上去。

设 $S(k, i)$ 表示当前有 $k$ 维，且第 $k$ 维是 $i$ 时超立方体内所有元素的和。

先来推几个式子：

结论 1：

$S(k, i) = S(k, i - 1) + S(k, i - 2)$

推导：

$\begin{aligned} S(k, i) =& \sum F(i_1 + i_2 + \cdots + i_{k - 1} + i - k + 1) \\ =& \sum F(i_1 + i_2 + \cdots + i_{k - 1} + (i - 1) - k + 1) + F(i_1 + i_2 + \cdots + i_{k - 1} + (i - 2) - k + 1) \\ =& \sum F(i_1 + i_2 + \cdots + i_{k - 1} + (i - 1) - k + 1) + \sum F(i_1 + i_2 + \cdots + i_{k - 1} + (i - 2) - k + 1) \\ =& S(k, i - 1) + S(k, i - 2) \end{aligned}$

结论 2：

$S(k, 1) = S(k - 1, n + 2) - S(k - 1, 2);$

推导：

$\begin{aligned} S(k, 1) =& \sum F(i_1 + i_2 + \cdots + i_{k - 1} + 1 - k + 1) \\ =& \sum_{t = 1}^n F(i_1 + i_2 + \cdots + t + 1 - k + 1) \\ =& \sum_{t = 1}^n F(i_1 + i_2 + \cdots + t - (k - 1) + 1) \\ =& \sum_{t = 1}^n S(k - 1, t) \\ =& S(k - 1, n + 2) - S(k - 1, 2) \end{aligned}$

结论 3：

$S(k, 0) = S(k - 1, n + 1) - S(k - 1, 1)$

推导过程同上。

然后我们要求的答案是 $\sum\limits_{t = 1}^nS(k, t)$ 即 $S(k + 1, 1)$ 。

我们该如何计算呢？

记二元组 $(S(k, 0), \ S(k, 1))$ ，设矩阵 $A$ 为斐波那契数列转移矩阵。

那么有：

$\begin{aligned} (S(k, 0), S(k, 1)) =& (S(k - 1, n + 1), S(k - 1, n + 2)) - (S(k - 1, 1), S(k - 1, 2)) \\ =& (S(k - 1, 1), S(k - 1, 2)) \times A^n - (S(k - 1, 1), S(k - 1, 2)) \\ =& (S(k - 1, 0), S(k - 1, 1)) \times (A^n - A) \end{aligned}$

所以预处理出 $B = (A ^ n - A)$ ，然后令 $(F(0), F(1)) \times B^k$ 就是答案了。

	#include <bits/stdc++.h>
	#define pb push_back
	#define pc putchar

	using namespace std;

	namespace IO{
	inline int read(){
	int x = 0, f = 1;
	char ch = getchar();
	while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
	while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
	return x * f;
	}

	template <typename T> inline void write(T x){
	if(x < 0) putchar('-'), x = -x;
	if(x > 9) write(x / 10);
	putchar(x % 10 + '0');
	}
	}
	using namespace IO;

	const int N = 1e6 + 10;
	const int mod = 1e9 + 7;
	int T, n, k;

	inline int add(int x) {return x >= mod ? x - mod : x;}
	inline int sub(int x) {return x < 0 ? x + mod : x;}
	inline int mul(int x, int y) {return 1ll * x * y % mod;}

	struct Matrix{
	int num[3][3];
	Matrix () {memset(num, 0, sizeof(num));}

	inline Matrix operator - (const Matrix &b) const{
	Matrix r;
	for(int i = 1; i <= 2; ++i)
	for(int j = 1; j <= 2; ++j)
	r.num[i][j] = sub(num[i][j] - b.num[i][j]);
	return r;
	}

	inline Matrix operator * (const Matrix &b) const{
	Matrix r;
	for(int i = 1; i <= 2; ++i)
	for(int j = 1; j <= 2; ++j)
	for(int k = 1; k <= 2; ++k)
	r.num[i][j] = add(r.num[i][j] + mul(num[i][k], b.num[k][j]));
	return r;
	}

	inline Matrix operator ^ (int p){
	Matrix r, a;
	memcpy(a.num, num, sizeof(num));
	for(int i = 1; i <= 2; ++i) r.num[i][i] = 1;
	for(; p; p >>= 1, a = a * a)
	if(p & 1) r = r * a;
	return r;
	}
	}f, A;

	inline void solve(){
	n = read(), k = read();
	f = ((A ^ (n + 1)) - A) ^ k;
	write(f.num[2][2]), puts("");
	}

	signed main(){
	#ifndef ONLINE_JUDGE
	freopen("test.in", "r", stdin);
	freopen("test.out", "w", stdout);
	#endif
	A.num[1][2] = A.num[2][1] = A.num[2][2] = 1;
	T = read();
	while(T--) solve();
	return 0;
	}

# B. 远行

一道 $\text{LCT}$ 加边维护树的直径板子题。

然而也可以用 $O(n \log^2n)$ 的并查集启发式合并水过去。

感觉也没什么好说的，就是并查集维护直径，然后启发式合并板子题。

直接放代码吧。

	#include <bits/stdc++.h>
	#define pb push_back

	using namespace std;

	namespace IO{
	inline int read(){
	int x = 0, f = 1;
	char ch = getchar();
	while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
	while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
	return x * f;
	}

	template <typename T> inline void write(T x){
	if(x < 0) putchar('-'), x = -x;
	if(x > 9) write(x / 10);
	putchar(x % 10 + '0');
	}
	}
	using namespace IO;

	const int N = 3e5 + 10;
	int typ, n, m, ans;
	int f[N][20], dep[N];
	vector <int> G[N];

	inline void dfs(int x, int fa){
	f[x][0] = fa, dep[x] = dep[fa] + 1;
	for(int i = 1; i <= 19; i++) f[x][i] = f[f[x][i - 1]][i - 1];
	for(auto v : G[x])
	if(v != fa) dfs(v, x);
	}

	inline int Dis(int x, int y){
	if(dep[x] < dep[y]) swap(x, y);
	int X = x, Y = y;
	for(int i = 19; i >= 0; i--)
	if(dep[f[x][i]] >= dep[y]) x = f[x][i];
	if(x == y) return dep[X] - dep[x];
	for(int i = 19; i >= 0; i--)
	if(f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];
	return dep[X] + dep[Y] - dep[f[x][0]] * 2;
	}

	struct Path{
	int s, t, dis;
	Path () {}
	Path(int _s, int _t) {s = _s, t = _t, dis = Dis(s, t);}

	friend bool operator < (Path a, Path b) {return a.dis < b.dis;}

	friend Path operator + (Path x, Path y){
	Path z = max(x, y);
	z = max(z, max(Path(x.s, y.s), Path(x.s, y.t)));
	z = max(z, max(Path(x.t, y.s), Path(x.t, y.t)));
	return z;
	}
	};

	struct Dsu{
	int fa, siz; Path p;
	} dsu[N];

	inline int find(int x){
	return dsu[x].fa == x ? x : dsu[x].fa = find(dsu[x].fa);
	}

	inline void merge(int u, int v){
	int x = find(u), y = find(v);
	if(dsu[x].siz < dsu[y].siz) swap(x, y), swap(u, v);
	G[u].push_back(v), G[v].push_back(u);
	dfs(v, u);
	dsu[y].fa = x, dsu[x].siz += dsu[y].siz, dsu[x].p = dsu[x].p + dsu[y].p;
	}

	inline int query(int x){
	int fx = find(x);
	return max(Dis(x, dsu[fx].p.s), Dis(x, dsu[fx].p.t));
	}

	signed main(){
	#ifndef ONLINE_JUDGE
	freopen("test.in", "r", stdin);
	freopen("test.out", "w", stdout);
	#endif
	typ = read(), n = read(), m = read();
	for(int i = 1; i <= n; i++) dsu[i].fa = i, dsu[i].siz = 1, dsu[i].p = Path(i, i);
	while(m--){
	int op = read(), u, v;
	if(!typ) ans = 0;
	if(op == 1) u = read() ^ ans, v = read() ^ ans, merge(u, v);
	else write(ans = query(read() ^ ans)), puts("");
	}
	return 0;
	}

# C. 珠宝

首先对 $c_i$ 相同的物品，按 $v_i$ 从大到小排序，然后记一个前缀和数组 $s_{i, j}$ 。

不难想到一个朴素 $\text{dp}$ 。

设 $f_{i, j}$ 表示单个物品价格不超过 $i$ ，且一共使用了 $j$ 元钱的最大价值。

转移方程： $f_{i, j} = \max\{f_{i - 1, j - k * i} + s_{i, k}\}$

不难发现 $j$ 和 $j - i * k$ 在模 $i$ 意义下相等，所以可以对 $\mod i$ 的值进行分类。

另外可以发现这个转移具有单调性，即如果 $j - k \times i$ 比 $j - p \times i (p > k)$ 更优，那么对于更大的 $j$ 来说 $j - k \times i$ 同样比 $j - p \times i$ 更优。

因为 $s_{i, j}$ 的增长率是递减的， $j - k \times i$ 的增长速度大于 $j - p \times i$ 。

可以用分治来实现。

	#include <bits/stdc++.h>
	#define pb push_back
	#define pc putchar
	#define int long long

	using namespace std;

	namespace IO{
	inline int read(){
	int x = 0, f = 1;
	char ch = getchar();
	while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
	while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
	return x * f;
	}

	template <typename T> inline void write(T x){
	if(x < 0) putchar('-'), x = -x;
	if(x > 9) write(x / 10);
	putchar(x % 10 + '0');
	}
	}
	using namespace IO;

	const int N = 1e6 + 10;
	const int K = 50010;
	int n, m, cnt;
	vector <int> s, a[310];
	int f[K], g[K];

	inline bool cmp(int a, int b) {return a > b;}

	inline int max(int x, int y) {return x > y ? x : y;}

	inline void solve(int l, int r, int L, int R, int p, int q){
	if(l > r) return;
	int mid = (l + r) >> 1, Mid = L;
	for(int i = max(L, mid - cnt); i <= min(R, mid); ++i){
	if(f[mid * p + q] < g[i * p + q] + s[mid - i])
	f[mid * p + q] = g[i * p + q] + s[mid - i], Mid = i;
	}
	solve(l, mid - 1, L, Mid, p, q), solve(mid + 1, r, Mid, R, p, q);
	}

	signed main(){
	#ifndef ONLINE_JUDGE
	freopen("test.in", "r", stdin);
	freopen("test.out", "w", stdout);
	#endif
	n = read(), m = read();
	for(int i = 1; i <= n; ++i){
	int c = read(), v = read();
	a[c].pb(v);
	}
	for(int i = 1; i <= 300; ++i){
	if(!a[i].size()) continue;
	sort(a[i].begin(), a[i].end(), cmp);
	s.clear(), s.resize(a[i].size() + 1);
	cnt = a[i].size();
	for(int j = 1; j <= (int)a[i].size(); ++j) s[j] = s[j - 1] + a[i][j - 1];
	memcpy(g, f, sizeof(f)), memset(f, 0, sizeof(f));
	for(int j = 0; j < i; ++j) solve(0, (m - j) / i, 0, (m - j) / i, i, j);
	}
	for(int i = 1; i <= m; ++i) write(f[i]), pc(' ');
	puts("");
	return 0;
	}

# A. 斐波那契

# B. 远行

# C. 珠宝

『学习笔记』中国剩余定理

20221211