永恒的奥古斯都(SCCPC 2026)

计数入门题。

转换之后不难发现 1→01\to 0 完全等同于 0→10\to 1 的逆操作。所以给定某种 0→10\to 1 的到达态问你可以有多少种初始态，完全等价于给定一个 1→01\to 0 的初始态问你可以有多少种到达态。

注意到对于根节点颜色为 11 的子树相对于颜色 00 自由度更高，所以可以猜测一下根节点颜色为 11 的子树的一些性质。不难猜测到当这个节点颜色变成 00 时，以该节点为根的子树的其他节点可以取到所有颜色的情况且完全独立。

若某个节点初始颜色为 11，那么下面的所有节点必定可以取到所有情况；某个节点初始颜色为 00，若祖先节点变化，使其颜色变成 11，然后同样可以让子节点取到所有情况。所以我们发现，关键在于祖先节点有没有变化。设两个状态分别为祖先节点有变化，和没有变化，然后转移即可。线性复杂度。

Senshuraku

来源：AT_abc463_f

难度：2127

挺考验基本功的一道题。

令 k=max⁡1≤i≤2Naik=\max_{1\le i\le 2N}a_i，最大值可能为 kk 或者 k+1k+1。根据这两种情况分类讨论。

当最大值为 k+1k+1 时，必然是某些 ai=ka_i=k 赢了成为 k+1k+1。经过讨论每组两个数 (x,y),x<y(x,y),x\lt y 的大小情况，我们得到如下几个种类：

1.x=y=kx=y=k，随机选一个都会贡献一个最大值 k+1k+1；

2.x<k,y=kx\lt k,y=k，选 yy 才会提供最大值 k+1k+1，否则不提供最大值；

3.y<ky<k，不会提供最大值 k+1k+1。

然后我们接下来分别枚举 aia_i 为最大值的时候。由于概率与最大值数量有关，所以我们需要知道最大值的数量。我们发现，对于除了 aia_i 所在组以外的组别，其是否提供最大值以及提供最大值的数量只与上文叙述组别种类有关。对于第 1 种最大值必然贡献 11；第 2 种根据提供最大值的数量，提供类似一个组合数状物的贡献；第 3 种最大值必然贡献 00。这里第 2 种的贡献数量是不确定的，假设贡献了 ii 个最大值，则最大值数量为 sum1+isum_1+i 。对于 ii 的系数是组合数，所以预处理组合数 + 枚举数量可以 Θ(n)\Theta(n) 算出。

当最大值为 kk 时，所有 ai=ka_i=k 全输了，可能会有部分 ai=k−1a_i=k-1 赢了成为 kk。同样进行分类：

1.x=y=kx=y=k，只要存在这样的组别就不可能实现，因为无论谁赢都会使最大值变成 k+1k+1；

2.x=k−1,y=kx=k-1,y=k，必须选 xx 才会提供两个最大值 kk；

3.x<k−1,y=kx<k-1,y=k，必须选 xx 才会提供一个最大值 kk；

4.x=y=k−1x=y=k-1，随机选一个都会贡献一个最大值 kk；

5.x<k−1,y=k−1x\lt k-1,y=k-1，必须选 yy 才会提供一个最大值 kk，否则不提供最大值；

6.y<k−1y\lt k-1，不会提供最大值 k+1k+1。

存在组别 1，那么无解。发现对于第 5 种是自由元，其他的贡献固定，所以可以类似处理 k+1k+1 的情况，假设贡献了 ii 个最大值，则最大值数量为 2sum2+sum3+sum4+i2sum_2+sum_3+sum_4+i 。同理预处理组合数 + 枚举数量。

那么此时我们的算法是 Θ(n2)\Theta(n^2) 的。注意到剩下的组的贡献仅与剩下组的各个种类数量相关，等同于 aia_i 当前所在组种类相关，所以实际上可以存下当 aia_i 当前种类不同时的答案，相同直接 Θ(1)\Theta(1) 引用，无需 Θ(n)\Theta(n) 做。可以优化到 Θ(n)\Theta(n)。

接下来大家自行推导吧，就不给出具体系数和代码了。自己推导挺好的。

Window Records

来源：AT_awtf2026algo_b

难度：?

有趣的高维 DP 题，Θ(n4)\Theta(n^4) 做法，吊打 std。

钦定在区间 [i,i+N−1][i,i+N-1] 内的 pp 有 max⁡i≤k≤pAk≤Ap\max_{i\le k\le p}A_k\le A_p 为区间 [i,i+N−1][i,i+N-1] 的关键点。考虑从右到左滑动窗口，此时只需要关注关键点的位置和数量即可。

具体地，当滑动窗口 [i+1,i+N][i+1,i+N] 到窗口 [i,i+N−1][i,i+N-1] 时，设区间 [k,k+N−1][k,k+N-1] 的集合为 S(k)S(k)，则 S(i+1)S(i+1) 变换到 S(i)S(i) 时会对原本的集合元素造成如下影响：

  • 若 S(i+1)S(i+1) 存在 i+Ni+N，则删去该元素；
  • 接着会删除 S(i+1)S(i+1) 的一段前缀（可能为空）；
  • 加入元素 ii。

不难发现，如果固定 A[N+1…2N−1]A_{[N+1\dots2N-1]} 以及 ∣S(i)∣|S(i)|，则 A[1,N]A_{[1,N]} 最多只有一种合法方案，即如果存在合法方案则摆设必然固定。所以我们把重点放在 A[N+1…2N−1]A_{[N+1\dots2N-1]} 上。关注到在 dp 转移时对于区间 [N+1,2N−1][N+1,2N-1] 只可能有删末尾和前缀。在删前缀的时候前缀具体的在 AA 上的位置我们并不关心，为了防止算重以及让后面填充前缀的自由度更高（即能有更多空间填充前缀），让当前前缀尽可能地往前填充，即填满 [N+1,k][N+1,k]。由于删前缀和删末尾元素是相对独立的两个操作，所以最好钦定一个删除顺序。发现让 [i,N][i,N] 的关键点更多，后面的自由度更高，所以尽可能先删末尾元素，然后删前缀。

设计 dp 状态：

fi,j,k,pf_{i,j,k,p}

表示处理到 S(i)S(i) 时在 [i,N][i,N] 区间有 jj 个关键点，在 [N+1,i+N−1][N+1,i+N-1] 区间有 kk 个关键点且填充部分前缀后还有 pp 的空间可以填充。转移的时候先考虑删除末尾元素，即 k→k−1,p→p−1k\to k-1,p\to p-1。然后是删前缀。注意这里删前缀要先把 jj 删到 11 才能开始同时减 k,pk,p。所以分别对 j,(k,p)j,(k,p) 两维做前缀和优化。如果没有变化，只需 p→p−1p\to p-1（因为被压缩了一个后缀空间）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
REP(k,0,a[n]-1)f[n][1][k][n-1]=1;
PER(i,n,2){
	memset(g,0,sizeof g); // 辅助转移数组
	REP(j,1,n-i+1)REP(k,1,i-1)REP(p,k,i-1){
		if(p-1>=k)add(f[i-1][j+1][k][p-1],f[i][j][k][p]); // 不需要做前缀和，即 S(i) 没有删除元素
		g[j+1][k-1][p-1]=f[i][j][k][p];
	}
	PER(j,n-i+1,1)REP(k,0,i-2)REP(p,k,i-2){ // 对 j 做前缀和
		add(g[j][k][p],g[j+1][k][p]);
	}
	PER(k,i-2,1)REP(p,k,i-2){ // 对 (k,p) 做前缀和
		add(g[1][k-1][p-1],g[1][k][p]);
	}
	REP(j,1,n-i+2)REP(k,0,i-2)REP(p,k,i-2){
		add(f[i-1][j][k][p],g[j][k][p]);
		if(j+k>a[i-1])f[i-1][j][k][p]=0; // j+k 为 |S(i)|，不能超过 a_i
	}
}
REP(p,0,n-1)add(dp[n][1],f[n][1][0][p]); // dp 为 [N+1,2N-1] 没有影响部分的转移
PER(i,n-1,1){
	REP(j,1,a[i+1])add(dp[i][j+1],dp[i+1][j]);
	PER(j,n,1)add(dp[i][j],dp[i][j+1]);
	REP(j,a[i]+1,n)dp[i][j]=0;
	REP(j,1,a[i])REP(p,0,i-1)add(dp[i][j],f[i][j][0][p]);
}
int res=0;
REP(j,1,a[1])add(res,dp[1][j]);