ARC106

可以叫刷题吧

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