ARC106 - Vps | Odalys = An Oier From Yali

可以叫刷题吧

# A

利用经典结论，一个数较小因子一定小于 $\sqrt n$ .

然后直接枚举即可

# B

搞个栈

# C

简单构造

拉棵生成树出来随便构造即可

这种跟无向图联通有关的第一时间想想生成树

# D

开始看错题了 \yun 所以函数任意怎么做啊

然后你一开始是 AB

最开始一定是直接加 f_

以 $f_{AB}=A$ 为例，另一种本质相同

那就是 AA...AB 这样的串了

若 $f_{AB} = A$ 那方案数唯一

看到这里，我们发现这是一个分讨题

否则，我们能构造出 A..BAABAB 这种可能有多个 B 但两两不交的形式

考虑 $f_{BA}$ 若为 B 那可以有很多 B 连续了，答案就是 2^

否则，考虑一个 dp_{u}{0] 放到 $u$ 颜色为 A/B 这样推推转移，发现就是 $fib n-2$

# E

~~这种奇怪的东西为什么会想到区间 $dp$ 呢？~~

~~所以是不是奇怪的限制都可以考虑区间 $dp$ 。~~

~~哦，限制可以简单被两边表示？~~
考虑设 $dp_{l,r}$ 表示 $l$ 和 $r$ 都被标记后，中间元素的期望个数

~~好像好多区间 $dp$ 都对两边特殊处理了？如 CSP2021 T2~~

这种区间 $dp$ 就是想到了转移就很简单了

可得转移柿子：

$dp_{l,r}={\sum_{a_k\in [l, r]} dp_{l,k} + dp_{k, r}\over |k|} + 1$

意思就是在中间找个可以标记的点打标记

一开始我还理解了那个 +1 好久，现在看来可能就是把每个标记点贡献全加即可，即 ${1\over k} \times k$ 就放外面了

这样 $n^3$ 信仰够的话可能能过

正经做法是搞个 $\texttt{BIT}$ 优化一下。

咋优化咧，大概是你在每个左右端点 $l,r$ 做短长度的时候，把所有 $k$ (那时还叫 $r$ ) 放在 $l$ 的 $\texttt{BIT}$ 上，要用的时候再区间查一下。

#include <bits/stdc++.h>
#define int long long
using namespace std;
template <typename T> inline void read(T &a){
	T w=1; a=0;
	char ch=getchar();
	for(;ch < '0' || ch > '9';ch=getchar()) if(ch == '-') w=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) a=(a<<3)+(a<<1)+(ch^48);
	a*=w;
}
template <typename T> inline void ckmax(T &a, T b){a = a > b ? a : b;}
template <typename T> inline void ckmin(T &a, T b){a = a < b ? a : b;}
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define mii map<int, int> 
#define pii pair<int, int> 
#define vi vector<int> 
#define Debug(x) cout << #x << " = " << x << endl
#define For(i,l,r) for (int i = l; i <= r; ++i) 
#define foR(i,l,r) for (int i = l; i >= r; --i)
const int N = 2020;
const int Mod = 1e9 + 7;
inline int Mul (int x, int y) {
	return (1ll * x * y) >= Mod ? (1ll * x * y % Mod) : (x * y); 
}
inline int Add (int x, int y) {
	return (x + y) >= Mod ? (x + y - Mod) : (x + y); 
}
inline int Sub (int x, int y) {
	return (x < y) ? (x + Mod - y) : (x - y); 
}
int n;
struct BIT {
	int a[N];
	inline void clear() {
		memset (a, 0, sizeof a); 
	}
	inline void upd (int x, int v) { for (; x <= n; x += (x & (-x))) a[x] = Add(a[x], v); }
	int ask (int l, int r) {
		if (l > r) return 0;
		int Ans = 0;
		for (; r; r -= (r & (-r))) Ans = Add(Ans, a[r]);
		l--;
		for (; l; l -= (l & (-l))) Ans = Sub(Ans, a[l]);
		return Ans; 
	}
} L[N], R[2];
int dp[N][N];
#define ll long long
int a[N], inv[N];
signed main() {
	read(n);
	For (i, 1, n) read(a[i]);
	a[0] = 0, a[n + 1] = n + 1;
	inv[1] = 1;
	for (int i = 2; i < N; i++) 	inv[i] = (ll) (Mod - Mod / i) * inv[Mod % i] % Mod;
	For (r, 1, n + 1) {
		R[0].clear(), R[1].clear(); 
		foR (l, r - 1, 0) {
			dp[l][r] = Add((R[0].ask(a[l] + 1, a[r] - 1)), (L[l].ask(a[l] + 1, a[r] - 1)));
			int k = R[1].ask(a[l] + 1, a[r] - 1);
			if (!k) dp[l][r] = 0;
			else dp[l][r] = (1ll * dp[l][r] * inv[k] + 1) % Mod; 
			if (l) {
				R[0].upd(a[l], dp[l][r]);
				R[1].upd(a[l], 1);
			}
			L[l].upd(a[r], dp[l][r]); 
		}
	}
	printf ("%lld\n", dp[0][n + 1]);
	return 0;
}

# F

~~限制我做不出 AT 的一大重要因素竟然是读不懂题？~~

考虑这种树上求点对最大距离的，一般都跟直径有关。

考虑树上的直径，若两点同色，那这种染色方案贡献一定就是直径长度了，其他点随意染色统计一下即可。

否则则为两点异色，那不妨统计每个点到直径两点距离记做点对 $(a, b)$ 。现在要做的就是给每个点选一个 $a$ 或 $b$ 然后求最大值

正着求显然不好，我们考虑求每个贡献的方案数，我们可以使用一个比较经典的套路，即从小到大依次算每个距离的贡献，也就是对于每个 $d$ ，求出 $ans \ge d$ 的方案数，把方案数累加起来就是答案啊

$ans\ge d$ 的不好求，我们可以转而求 $ans\le d$ 的方案数，那么，对于每个 $d$ 若存在一个点对的 $min(x, y)$ 都大于 $d$ ，那方案数为 $0$ ；否则方案数即为两个值都小于 $d$ 的点两个任意选，也就是一个 $2$ 的次幂形式。

#include <bits/stdc++.h>
using namespace std;
template <typename T> inline void read(T &a){
	T w=1; a=0;
	char ch=getchar();
	for(;ch < '0' || ch > '9';ch=getchar()) if(ch == '-') w=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) a=(a<<3)+(a<<1)+(ch^48);
	a*=w;
}
template <typename T> inline void ckmax(T &a, T b){a = a > b ? a : b;}
template <typename T> inline void ckmin(T &a, T b){a = a < b ? a : b;}
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define mii map<int, int> 
#define pii pair<int, int> 
#define vi vector<int> 
#define Debug(x) cout << #x << " = " << x << endl
#define For(i,l,r) for (int i = l; i <= r; ++i) 
#define foR(i,l,r) for (int i = l; i >= r; --i)
const int N = 2e5 + 10;
const int Mod = 1e9 + 7;
inline int Mul (int x, int y) {
	return (1ll * x * y >= Mod) ? (1ll * x * y % Mod) : (x * y); 
}
inline int Add (int a, int b) {
	return (a + b >= Mod) ? (a + b - Mod) : (a + b); 
}
inline int Sub (int a, int b) {
	return (a < b) ? (a + Mod - b) : (a - b); 
}
int qpow (int a, int b) {
	int base = a, ans = 1;
	while (b) {
		if (b & 1) ans = Mul(ans, base);
		base = Mul(base, base);
		b >>= 1;
	}
	return ans;
}
struct edge {
	int to, nxt;
} e[N << 1];
int head[N], cnt, n;
inline void add (int u, int v) {
	e[++cnt].to = v; e[cnt].nxt = head[u]; head[u] = cnt;
}
int dep1[N], dep2[N];
void dfs(int u, int fa, int *dep) {
	for(int i = head[u]; i; i = e[i].nxt) {
		int v = e[i].to; 
		if(v != fa) {
		dep[v] = dep[u] + 1;
		dfs(v, u, dep);
	}}
}
int dep[N], pw[N], pre[N], L, R; 
int main() {
	read(n);
	For (i, 1, n - 1) {
		int u, v; read(u); read(v); add(u, v), add(v, u);
	}
	dfs(1, 0, dep);
	L = std::max_element(dep + 1, dep + n + 1) - dep;
	dep[L] = 0; dfs(L, 0, dep);
	R = std::max_element(dep + 1, dep + n + 1) - dep;
	pw[0] = 1;
	for(int i = 1; i <= n; i++) pw[i] = (pw[i - 1] << 1) % Mod;
	dfs(R, 0, dep2);
	int lower = 0;
	for(int i = 1; i <= n; i++) {
		if(i == L || i == R) continue;
		lower = std::max(lower, std::min(dep[i], dep2[i]));
		pre[std::max(dep[i], dep2[i])]++;
	}
	for(int i = 1; i < n; i++) pre[i] += pre[i - 1];
	int ans = 1ll * pw[pre[lower]] * lower % Mod;
	for(int i = lower + 1; i < n; i++) {
		ans = (ans + 1ll * i * (pw[pre[i]] - pw[pre[i - 1]] + Mod) % Mod) % Mod;
	}
	ans = (ans * 2 + 1ll * dep[R] * pw[n - 1]) % Mod;
	printf("%d\n", ans);
}

网上一个博主的代码，吊打我几百行 /kk

# A

# B

# C

# D

# E

# F

2021-10-29-Test

2021-10-30-Test