constexpr int MAXN = 2e5 + 5;
int n, a[MAXN], b[MAXN];

signed main() {
scanf("%lld", &n);
for (int i = 1; i <= n; i++) scanf("%lld", a + i);
iota(b + 1, b + n + 1, 1);
int sum = 0;
for (int i = 1; i <= n; i++) sum += a[i] * b[i];
if (sum == 0) {
puts("Yes");
for (int i = 1; i <= n; i++) cout << b[i] << ' ';
cout << '\n';
} else if (sum < 0) {
int sma = 0, i;
for (i = 1; i <= n && sma >= 0; i++) sma += a[i];
--i;
if (sma < 0) {
puts("Yes");
for (int j = 1; j <= i; j++) cout << b[j] + sum << ' ';
for (int j = i + 1; j <= n; j++) cout << b[j] << ' ';
cout << '\n';
return 0;
}
for (i = n; i >= 1 && sma <= 0; i--) sma += a[i];
++i;
if (sma > 0) {
puts("Yes");
for (int j = 1; j < i; j++) cout << b[j] << ' ';
for (int j = i; j <= n; j++) cout << b[j] - sum << ' ';
cout << '\n';
return 0;
}
puts("No");
} else {
int sma = 0, i;
for (i = 1; i <= n && sma <= 0; i++) sma += a[i];
--i;
if (sma > 0) {
puts("Yes");
for (int j = 1; j <= i; j++) cout << b[j] - sum << ' ';
for (int j = i + 1; j <= n; j++) cout << b[j] << ' ';
cout << '\n';
return 0;
}
for (i = n; i >= 1 && sma >= 0; i--) sma += a[i];
++i;
if (sma < 0) {
puts("Yes");
for (int j = 1; j < i; j++) cout << b[j] << ' ';
for (int j = i; j <= n; j++) cout << b[j] + sum << ' ';
cout << '\n';
return 0;
}
puts("No");
}

return 0;

}

</details>

# 7/25

## 总结

成绩不错，没有挂分。这次学到的 trick 下次要注意，还有就是理解 T2 贪心的思路。

## T1 Permutations & Primes

瞪眼规律题。本人题解[在此](https://gxyzoj.com/d/hzoj/p/3824/solution/66a1d4551a76fc19c6abb5d1)。

## T2 [[ARC116E] Spread of Information](https://www.luogu.com.cn/problem/AT_arc116_e)

部分分是显然的：$k=1$ 树的直径，$k=n-1\lor n\le5$ 输出 `1`，30pts 到手。

剩下就是一眼的二分答案，但怎么二分是个问题。容易发现的是我们需要在 $O(n)$ 的时间内完成 check，易得判断能否使用 $k$ 个点使得答案不超过二分的 $\textit{mid}$。接下来就是考场上没有想到的了：**对于任意一个点，最优情况是覆盖它的那个点也同时覆盖了尽可能多的点**，易得覆盖点在它的 $\textit{mid}$ 级祖先是最优的。具体的，就是[这篇文章](https://www.luogu.com.cn/article/oqk4o0m8)的内容了。

## T3 [Ball Collector](https://gxyzoj.com/d/hzoj/p/3826?tid=66a1011c1a76fc19c6aafd30)

主要是套路，**处理不能同时选择的两个点的 trick 通常是将这两个点连边，然后就转化成了边向边上节点二取一的问题**。这点 trick 以后要注意。

剩下的什么*可撤销并查集*就不是重点了，题出的也是够好的。

## T4 [P7028 [NWRRC2017] Joker](https://www.luogu.com.cn/problem/P7028)

~~题外话：教练出这题的时候竟然还和饿殍联动了~~

名字叫 Joker，题也很 Joker，挖坑。

# 7/26

## 总结

T2 的 40pts 只骗到了 20pts，还差**进一步的推理**。

T3 一眼熟悉，但括号序列的码量难以调试，直到我知道还能**线段树维护直径**。线段树是我认为我自己最熟练的数据结构，如何将一些图论问题转化为线段树，这道题给了我们一个提示。

T4 的暴力没能打上，其实状压的思路已经有了，但我拿 DFS 又 R 又 WA 的，于是放弃了。全场也只有 LMX 大佬打出来了，学习学习。

## T1 y

两眼题，BFS 还是各种乱搞都能过。~~两眼题是因为我刚开始以为这题不可做。~~

## T2 s

看[知播题解](https://gxyzoj.com/d/hzoj/p/3821/solution/66a3481d1a76fc19c6ada276)。关于此题想说的已经在上面了。

## T3 p

这题一眼就看得出来就是 P2056 的变式，只不过加了一个区间查询而已。P2056 的做法很多，如果我当时能在做那道题的时候看到线段树维护直径这个方法，也不至于这次死调括号序列……不过线段树维护直径**只能用于非负权边**，类似 Dijkstra。

首先我们要维护黑点的数量，白点我们是不看的。维护每个点的颜色，一旦有黑点加入，就要更新。此题相较于 P2056 增加了区间查询，所以需要用线段树或树状数组维护区间。由于是单点修改、区间查询，选择树状数组是最经济的方式。*主要还是被卡空间卡怕了。*

我们的线段树是维护区间黑点之间的直径的。每加入一个黑点，就在线段树上做修改。这里有一个结论：对于两个点集 $S,T$，他们的直径集合分别为 $f(S),f(T)$，则有
$$
f(S\cup T)\subseteq f(S)\cup f(T)
$$
换句~~人~~话说，假设 $S$ 的直径端点为 $u_1,v_1$，$T$ 的直径端点为 $u_2,v_2$，则 $S\cup T$ 的直径端点仅可能存在于 $u_1,v_1,u_2,v_2$ 这四个点中的任意两个中。证明很简单。那么我们就可以用线段树维护一个区间的 $u,v$ 和 $\textit{dis}$，其中 $\textit{dis}$ 表示 $\text{dis}(u,v)$，也就是直径。区间合并的时候在左右儿子的 $u,v$ 中四选二取 $\textit{dis}$ 的最大值即可。

注意，$\text{dis}(u,v)$ 的计算需要用到 LCA 的计算。这里倍增由于自带一个 $\log$ 的常数，套在线段树里会 **TLE 地死死的**，所以请务必使用树剖或 ST 表求 LCA，我更倾向于树剖求，好写好调好背。

## T4 [[ARC096E] Everything on It](https://www.luogu.com.cn/problem/AT_arc096_c)

### 题意

对于集合 $\{1,2,\dots,n\}$，求它的子集族中，有多少个子集满足：

1. 任意两个子集互不相同；
2. $\forall i\in[1,n]$，$i$ 都在其中出现了至少 $2$ 次。

### 解析

这题就涉及到我还不会的知识了：**斯特林数**。咱先从头来看这个题。

设 $\textit{dp}_i$ 表示已经有确定的 $i$ 种元素不合法，其它 $(n-i)$ 种元素任意的方案数，容斥，答案为
$$
\sum_{i=0}^n(-1)^n\binom ni\textit{dp}_i
$$
既然 $\textit{dp}_i$ 中的元素被鲜明地分成了两类，设 $f_i$ 表示确定的 $i$ 种元素不合法元素的方案数，有
$$
\textit{dp}_i=2^{2^{n-i}}f_i
$$
其中 $2^{2^{n-i}}$ 意为：$(n-i)$ 种元素构成了 $2^{n-i}$ 个集合，而这些集合又作为元素构成了 $2^{2^{n-i}}$ 个集合。这里求解这个需要用到欧拉定理，转化为求解 $2^{2^{n-i}\bmod\mathrm{MOD-1}}\bmod\mathrm{MOD}$。

现在压力给到求 $f_i$，考虑这 $i$ 个元素分别放到了哪些集合里，而表示**将 $\boldsymbol i$ 个元素放到 $\boldsymbol j$ 个集合里的方案数就是第二类斯特林数的定义**。它的递推式为：
$$
{i\brace j}={i-1\brace j-1}+j{i-1\brace j}
$$
但只用斯特林数递推略有问题，由于限制是不多于一次，意味着可能存在一些数没有出现过。我们考虑新加入一个集合当做 “垃圾堆”，该集合中的数即为没有出现的数。但是还有一个问题：“垃圾堆” 可能为空。所以我们新加入一个数字 $0$，$0$ 所在集合即为垃圾堆。

所以有
$$
f_i=\sum_{j=0}^n\left(2^{n-i}\right)^j{i+1\brace j+1}
$$
层层回代，得到答案式
$$
\textit{ans}=\sum_{i=0}^n(-1)^i\cdot2^{2^{n-i}}\binom ni\sum_{j=0}^i{i+1\brace j+1}\cdot\left(2^{n-i}\right)^j
$$

### 评价

写的很仓促，不完全理解。

# 7/27

## 总结

不是很理想。答题节奏有点小问题，前 1/3 场在怼 T4 的打表，最后也就比一般人多打了 4pts。然后后 2/3 场一直在怼 T3 的组合数学，结果还没 CQL 的暴力 DP 高。最后 T1 的 20pts 暴力和 T2 的 20pts 暴力拢共只拿了 10pts，rnk14 草草收场。

- T1 看到概率期望心里很慌，也许是好长时间没打了导致忘了。其实 50pts 的 DP 还是很好想的，如果此时的我是刚刷完不少概率期望的我也许能打出来（我记得有段时间特爱考概率期望）。再往后 80pts 的矩阵快速幂不是我的强项，考场上真正拿到 >50pts 的人为零，所以也不做要求了。
- T2 其实比较温和（听 WZW 大佬讲过之后觉得），但考场上能推出来的难度可能真的只有 WZW。不过 20pts 的暴力太可惜了，最重要的是我的代码 *CE* 了，因为**毫秒级别随机数不能在 Linux 下使用**。这点其实能在 CSP 之前发现是非常非常庆幸的，别到时候一个 `_timeb` 把一整套代码全葬送了。
- T3 一眼高级组合数学，就一直死怼，不过没想到卡特兰数，因为打太久了忘了。$\textit{typ}=1$ 的 25pts 非常显然，$\textit{typ}=2$ 的 DP 推了不少时间，$\textit{typ}=3$ 推了很久，最后 $\textit{typ}=0$ 没时间推了。原本 75pts 还变成了 60pts，因为**没开 long long**。
- T4 一眼不会，*STZ 大佬场切非常佩服*，我就剩下打表了，最后比一般人多打了 4pts，其实还能再多打 2pts，不过这不重要。

总之，*这场比赛是非常有教育意义的*。**概率期望、矩阵快速幂、组合数学**，这些都是考出来非常拉分的知识点，必须掌握。

## T1 随

- 10pts：$\textit{mod}=2$，直接输出 `1` 拿下；
- 20pts：$n=1$，直接输出 $a_1^m\bmod\textit{mod}$ 拿下；  
  *还是答题节奏的问题，考场上没用快速幂导致这 10pts 失手。*
- 50pts：考虑 DP。设 $\textit{dp}_{i,j}$ 表示考虑到第 $i$ 个数，当前结果为 $j$ 时的答案，有 DP 方程
  $$
  \textit{dp}(i,j)=
  $$

## T2 单

- 10pts：经典 LCA 暴力求树上距离；
- 20pts：$a_i\le20$，考虑暴力枚举；
- 40pts：考虑 up-and-down 求 $b$ 数组。先一遍 DFS 求出一个 $\textit{sum}$ 数组，$\textit{sum}_i$ 表示 $i$ 的子树的点权和。随后我们就有一个方程：
  $$
  b_i=b_\textit{fa}-\textit{sum}_i+(\textit{sum}_\textit{rt}-\textit{sum}_i)=b_\textit{fa}+\textit{sum}_\textit{rt}-2\textit{sum}_i
  $$
  我们发现我们只需要知道 $b_\textit{rt}$ 就可以求出整棵树的 $b$ 数组，而 $b_\textit{rt}=\sum_{i=2}^n\textit{sum}_i$，进而得解。
- 100pts：也就是 $t=1$ 的情况，需要我们通过 $b$ 数组求解 $a$ 数组。乍一看很难，关键点就在于我们刚推出的那个式子：
  $$
  b_i=b_\textit{fa}+\textit{sum}_\textit{rt}-2\textit{sum}_i
  $$
  移项得
  $$
  b_i-b_\textit{fa}=\textit{sum}_\textit{rt}-2\textit{sum}_i
  $$
  只要求出 $\textit{sum}_\textit{rt}$，$b$ 是我们已知的，所以就可以求出 $\textit{sum}_i$，进而差分出 $a_i$。

  每个除根节点以外的节点都有这个式子，也就是 $(n-1)$ 个这样的式子，**把它们求和：**
  $$
  \sum_{i=1}^nk_ib_i=(n-1)\textit{sum}_\textit{rt}-2\sum_{i=2}^n\textit{sum}_i
  $$
  其中 $k_i$ 是根据树的结构决定的系数，我们只需一遍 DFS，每遍历到一个节点给 $k_i\gets k_i+1,k_\textit{fa}\gets k_\textit{fa}-1$ 就可以求出。移项有
  $$
  \textit{sum}_\textit{rt}=\frac1{n-1}\left(\sum_{i=1}^nk_ib_i+2\sum_{i=2}^n\textit{sum}_i\right)
  $$
  后面那个看起来很难求，但请注意前面我们已经推过的某一式子，可知：**这个玩意就是 $\boldsymbol{b_1}$**。

  然后就求出来了。

### 评价

WZW 大佬真的非常善于推式子啊。

## T3 题

高级组合数学，这题的部分分非常明显，主要在于求组合数。*其实想到卡特兰数又能如何呢，你卡特兰数还不是得拿组合数求。不过如果能看出来卡特兰数，不失为一种猜结论的方法。*

主要学习的还是 CQL 的 DP，这个技巧非常实用，定义 $f_{i,j,k}$ 为 $i$ 步之后走到 $(j,k)$ 的方案数。但这是 $O(n^3)$ 的，要做到 $O(n^2)$ 我们看到 CQL 同志在 $\textit{typ}=2$ 时的转移：

```cpp
dp[0][1000] = 1;
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= 4000; j++) {
        if (j == 1000)
            dp[i][j] = (dp[i - 1][999] + dp[i - 1][1001] + dp[i - 1][2001] + dp[i - 1][3001]) % mod;
        else if (j == 999)
            dp[i][j] = (dp[i - 1][1000] + dp[i - 1][998]) % mod;
        else if (j == 1001)
            dp[i][j] = (dp[i - 1][1000] + dp[i - 1][1002]) % mod;
        else if (j == 2001)
            dp[i][j] = (dp[i - 1][1000] + dp[i - 1][2002]) % mod;
        else if (j == 3001)
            dp[i][j] = (dp[i - 1][1000] + dp[i - 1][3002]) % mod;
        else 
            dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % mod;
    }
cout << dp[n][1000] << "\n";

当时他讲了，不过现在也不太记得了。

T4 DP搬运工1

比较新颖的 DP 转移方式，叫预设型 DP，它的一个点在于对于一个序列 \(\texttt{[....1..23...4......]}\) 的情况，中间的 \(\texttt .\) 可以有无数个，我们不关心有多少个空位，只关心能否将新元素插入任意一个空位中，具体插入后空位的情况我们再分讨。

当然，考试上几乎没有人能想出这个转移的，更多的人还是采取暴力 + 打表的方式，毕竟能骗两分是两分。

7/29

这场比赛是稳定的，有挂分但不多，保住了祖传 rnk8 的好成绩，但 T4 的挂分并非不可查，还是要多检查啊。

T1 [ARC148A] mod M

简单题，易发现模数为 \(2\) 的时候肯定是最优的，所以全输 1 或 2 就有可观的分数。经测试，全输 1 拿 59pts，2 拿 41pts，随机输刚好 50pts。

但在某些情况下模数为 \(2\) 并不优，当且仅当这些数对某一个模数是同余的。所以排序然后 gcd 判一下相邻数之间的差即可。

T2 [ARC107D] Number of Multisets

T2 是臭名昭著的 \(998244353\)，也是 DP 题。转移很神仙，具体地，如果所有数凑成了 \(\boldsymbol j\)，那么只需全部除以二就能凑成 \(\boldsymbol{j/2}\)，所以 \(f_{i,j}\) 表示 \(i\) 个数和为 \(j\) 的方案数，转移：

T3 [ARC149D] Simultaneous Sugoroku

• 暴力的 47pts 很可观；
• 此题的 trick：将移动波特转化为移动原点，同时观察移动中在原点两侧的不变的量及时剪枝，从而减少枚举。

T4 [ICPC2018 WF] Triangles

• 这题让我想到南蛮图腾，不过显然比那题单纯的模拟要难得多；
• 树状数组维护的做法很 D，考场上能保证自己的暴力不写挂就不错了；
• 暴力有 50pts。

7/30

炸废了。还是考场上不够细心，更多地去推难题的高级部分分 / 正解，从而简单题上挂了分。

T1 [ARC124B] XOR Matching 2

不难，我们发现要想减少枚举，就从枚举结果入手，此题的结果只能是 \(n\) 的复杂度，分别用 \(a_1\) 去异或 \(b_i\)，然后暴力检查这个结果能否匹配上剩余的 \(b_j~(j\ne i)\)，如果能匹配上答案就累加，一定一定要对答案去重。

具体可以对 \(a,b\) 数组都排序，可以减少暴力检查的复杂度。

T2 S

很可惜的一道 DP，推了最长时间，也是挂分最多……

显然的一点是，抽屉原理，如果一个球的数量超过了 \(\lceil n/2\rceil\)，那一定是无解。然后考虑每个球给总答案的贡献，设 \(\textit{dp}_{i,j,k}\) 表示三种颜色的球都填多少了，但是这样没法转移，因为这题还要求同种颜色不相邻，那么再设一维变成 \(\textit{dp}_{i,j,k,0/1/2}\) 表示最后填的球的颜色。因为同种颜色是不可能交换的，所以每个球要交换到 “不丑” 需要走逆序对的数量，而这个逆序对我们可以通过处理一个 \(\textit{sum}_{0/1/2,i}\) 表示前 \(i\) 个位置三种颜色球的总和、\(\textit{pos}_{0/1/2,i}\) 表示总和为 \(i\) 时三种颜色的球的位置，然后转移：

其他情况的转移同理。

考完试检查发现还是转移的地方有漏，加上一定要滚动数组优化空间。

T3 [ARC124E] Pass to Next

很 D 的一道题。

T4 [JOI 2020 Final] 火事 / 火事 (Fire)

我参考的是这篇的乱搞做法。相关正在研究。具体而言，用 list 维护递减段是很新颖的，以前对 list 不是很了解，以后可以多了解一些奇技淫巧。

7/31

rnk2，刷新纪录了。不过 bobo 说考的好是因为打的顺，所以也没什么可骄傲的。

T1 黑客

枚举答案，老套路了。我们枚举最终约分好的分子和分母，用 \(A,B,C,D\) 分别除以它们，得到两段区间，取区间的交集累加答案，时间复杂度 \(O(999^2)\)。

T2 密码技术

上来先看题：又是一道 \(998244353\)……

不过再一看数据范围：\(n\le50\)，这不是标准乱搞么。我们仔细观察这个题，首先我们知道，如果有 \(\boldsymbol x\) 行（列）可以交换，那么它们会给答案有 \(\boldsymbol{x!}\) 的贡献。我们又发现，行的方案数和列的方案数是互不影响的。所以这题看似 \(998244353\)，实际上就是很简单的计数。

接下来看怎么统计。我们重点是要知道能相互交换的行（列）数。既然数据这么水，对于任意两行（列）能否交换我们直接暴力 \(O(n^3)\) 求即可。我们发现若 \(a,b\) 两行能交换，\(b,c\) 两行能交换，那么 \(a,b,c\) 三行都能交换。所以就很自然地并查集处理。然后这题就做完了。

T3 [HNOI2015] 亚瑟王

出题人包装题面的能力是越来越高了，不过还是被我搜样例找到了原题。

45pts 的状压本以为稳了，没想到需要优化，否则只有 11pts。具体而言，我们原本是要枚举 \(s\in[0,2^n-1]\)，但其实我们没有必要枚举这么多，稍微存一下每个状态的点就可以优化。