SYC2022 比赛题解合辑（Day 1~5）

Day 1 T1 求和

$A$ $T(A)$ $T$ 如下所示：


xxxxxxxxxx
12
1
vector <int> T(vector<int> A){
2
 vector <int> B;
3
 int n=A.size(), i, j, k;
4
 for (i=0; i<n; i++){
5
     for (j=0; j+i<n; j++){
6
         int mx=A[j];
7
         for (k=j; k<=i+j; k++) mx=max(mx, A[k]);
8
         B.push_back(mx);
9
     }
10
 }
11
 return B;
12
}

$T(T(A))$ $10^9+7$ $n\le 10^5$ 。

Day 1 T2 游戏

Alice 和 Bob 正在玩游戏，游戏规则如下——
$n$ 的字符串，每次操作只能为以下二者之一：
删去一个字符。
将当前字符串打乱，重新排列为此前没有出现过的一个新字符串。
Alice 先手，首先删完字符串的人获胜，两人都绝顶聪明，会按照最优策略行动。
$\{1,2,...,k\}$ ，总共有多少种字符串能够使自己获胜？
$19260817$ 取模后输出（这是一个质数）。

经过艰苦卓绝的打表，我们发现先手几乎是必胜的。只有一种情况下后手可以翻盘，那就是初始的字符串的可重排列数是一个奇数。我们使用归纳法证明：

若当前字符串的排列种类数为奇数，那么由于可重排列的性质，任意删去一个字符产生的新字符串排列数都是偶数，即递归意义上的必胜态；所以不管是先后手，其目标都是不删数。但是由于总数是奇数，所以先手不得不去删数，从而使得后手进入了必胜态。
若当前字符串的排列数是偶数，继续分类讨论：若存在一个字符使得删掉后是一个必败态，那么作为先手肯定会抢先删掉那个字符；若不存在，则双方都会去极力避免进入后继状态，而后手由于奇偶性会被迫进入。

$n$ $n$ $n$ $a_i$ $0$ $n$ $a_1$ a $a_2$ 个 b……这样的一个字符串就是合法的。

$f(x)=\sum_{s} x^s\cdot \frac 1{s!}$ $s!$ $n$ $f^n(x)$ 。（在不交并卷积的意义下）。

$\log^3$ $g=f^n$ $n\log^2{n}$ 。

$O(n^{1.58})$ $O(3^{\log_2{n}})$ ）。

Day 1 T3 染色

$n$ $n-1$ $m$ $col_i(1 \le col_i \le m)$ $2 \le i \le n$ $i$ $i$ $p_i (1\le p_i < i)$ $1$ 的有向边。
$q$ $t$ $v_1,v_2,...,v_t$ $1$ 次），但是，为了拒绝内卷，他们约定，到达集合节点后，每个人的调色板上颜色数量应当相同；同时，为了避免重复劳动，他们还约定，任意两个人的调色板上不能有相同颜色。
$1 \le n \le 300000,1 \le m \le 1000,1 \le q \le 50000,2 \le t \le 5$ 。

$\log$ ）。

Hall $\frac 1w \cdot \log{n}\cdot q\cdot 2^t\cdot m$ 。由于每次 bitset 计算出来的结果是一样的，所以可以再少一个二分。

这启示我们，OI 做题中不能过度依赖题目性质，在合适的时候就应该诉诸工业解法。工业解法和思维解法必须两者同时灵活运用，且训练上要达到一种平衡。

Day 2 T1

$n$ $i$ $a_i$ $h_i$ $b_i$ 。
$m$ $m$ $0$ ，则它死亡，并且它两边的随从会靠在一起成为相邻关系。
$i$ $a_i$ $b_{i−1}+b_{i+1}$ $n\le 400$ 。

$a$ $b_{mid}$ 的额外攻击。直接区间 dp 即可。

Day 2 T2

$n,m$ $2m$ $a$ 满足：
$∀1≤i≤2m,a_i∣n$
$\prod^{2m}_{i=1}a_i≤n^m$
$998244353$ $1≤n≤10^9,1≤m≤100$ 。

$2m$ $n^m$ $\prod \frac n{a_i}\ge n^m$ $n^m$ 的方案数即可。

显然每个质因数是彼此独立的，而每个质因数就相当于是把一些相同的物品分给有编号的人，且每个人有个背包大小上限。直接容斥，枚举有多少人超出上界即可。

Day 2 T3

$k$ $n$ 的序列的归并为：
$A$ $kn$ $A$ 的末尾。
两个归并不同，当且仅当存在某次操作，选取的序列标号不同。
$A$ $k$ 的子串，使得这个子串中的数为同一个数。
$m$ $n$ $f(l,r)$ $[l,r]$ $\sum^{m}_{i=1}\sum^m_{j=i+1}f(i,j)$ $998244353$ 的值。
保证测试数据随机生成。 $1≤n,m≤300$ 。

$(i,j)$ ，我们枚举哪些颜色构成不合法，进行一个服从子集反演的容斥。显然这些颜色必须满足彼此的相对位置相同；计算方案时，在两个颜色间的部分构成一个可重排列，直接计算即可。

$j-i\ge 30$ $O(n^3)$ 。

$j-i+1\in[5,30]$ $1s$ 左右。

$j-i+1\in [2,4]$ $f_j$ $j$ $O(m^3\cdot C)$ 完成这一部分。

$j$ 。

Day 3 T1

$z$ $z=0$ 。
$n$ $0$ $k$ $p_t$ $t$ $z:= z+t$ 。
$\min(z, x)$ $998244353$ $1\le n\le 10^7, 1\le k\le 100, 1\le x\le \min(10^7, \frac{5\times 10^7}{k}), 1\le a_i\le 100$ 。

见 https://lllpoiuy.github.io/Lsh-WeBlog/%E7%BA%BF%E6%80%A7%E4%BB%A3%E6%95%B0%E4%B8%8E%E5%A4%9A%E9%A1%B9%E5%BC%8F.html 中的 Example 12。

Day 3 T2

$n$ $m$ $(a_i, b_i)$ $b_i$ $a_i$ $m$ $1\le n\le 2000, 1\le m\le \min(n^2, 5\times 10^5), 1\le a_i, b_i\le n$ ，所有可行数对互不相同。

$1$ $-1$ $\bmod 2$ $1$ $0$ ；由题目中的条件就得到矩阵满秩。

$O\left(\frac 1w\cdot n^3\log{n}\right)$ 。

$M_{i,j}$ 的求法。而伴随矩阵就等于代数余子式构成的矩阵的转置，满足：

\operatorname{adj}(A)=\det(A)\times A^{-1}

$O(\frac 1w\cdot n^3)$ 的复杂度。

Day 3 T3

$\text{Y}$ 国队的生死战，他们只有获得胜利才能出线。
$n$ $i$ $\left[0,a_i\right]$ $i$ $x_i$ $\left(\sum_{i=1}^n x_i\right)^m$ $\text{Y}$ 夫希望能够计算出这场比赛他们期望下能够发挥出多少的战力。
$998244353$ $n,m\leq 10^5$ 。

$\prod_{i=1}^n x_i^{a_i}$ $\sum a_i=m$ $\prod\limits_{i=0}^n\frac {a_i^{b_i}}{b_i+1}\cdot \frac 1{b_i!}$ ，前半部分是积分的结果，后半部分是可重排列的一部分。

为了快速统计，我们将其写作生成函数的形式：

m![x^m]\prod\limits_{i=1}^n\left(\sum\limits_{j=0}^n{\frac {a_i^j\cdot x^j}{(j+1)!}}\right)=m![x^m]\operatorname{exp}\left( \sum_{i=1}^n\ln\left( \sum_{j=0}^n\frac{a_i^jx^j}{(j+1)!} \right) \right)

$\ln\left( \sum_{j=0}^n\frac{x^j}{(j+1)!} \right)=\sum_{i=0}^mp_i\cdot x^i$ $p_i$ $a_j$ $i$ 次方和。

$\sum_{i=1}^n\frac 1{1-a_ix}$ 。可以分治地通分并求和。

Day 4 T1

$F(x)$ $x$ $F(6)=2$ $F(8)=1$ $6$ $2,3$ $8$ $2$ ）。
$n$ $(1 \le n \le 10^5)$ $A=\{A_1,A_2,...,A_n\}$ $10^7$ 的正整数。
$q$ $L,R$ $\sum_{i=L}^{R} \sum_{j=i+1}^{R} F(\gcd(A_i,A_j))$ 。
$\gcd(a,b)$ $a,b$ $1 \le n \le 100000, 1 \le q \le 100000, 1 \le x \le 10^7$ 。

$i$ $cnt_i$ $\frac 12 cnt_i\cdot (cnt_i-1)$ $O(n^{1.5}\cdot \omega(V))$ 维护即可。

Day 4 T2

$n(1 \le n \le 10^5)$ $0$ 。
$m(1 \le m \le 10^5)$ 次更新 ——
$x_1,x_2,y_1,y_2,w(1 \le x_1 \le x_2 \le n, 1 \le y_1 \le y_2 \le n,-10^6 \le w \le 10^6)$ 的五个参数表示,
$x_1 \le i \le x_2, y_1 \le j \le y_2$ $(i,j)$ $i$ $j$ $w$ $(i,j),(j,i)$ $2w$ ），在所有更新结束后，询问 —— 在最小化所修道路数量的基础上，能够保证 A 国任意两个城市可以互相到达的最小总代价是多少？
每个测试点有多组数据。

$O(n\log^2{n})$ 。

B 算法的精髓就在于可以放心的重构，重构的过程中可以承载大量信息；而处理标号不同的最经典方式就是维护最大值和次大值。

Day 4 T3

$n$ $c=c_1c_2....c_n$ ，因为担心被窃听，因此对信息进行了加密，加密方式如下 ——
$n$ $a_1,a_2,...a_n$ $i$ $a_i > \sum_{j=1}^{i-1} a_{j}$ $\sum_{i=1}^{n} a_i < q = 2^{64}$ 。
$r$ $b_1,b_2...b_n$ $b_i \equiv a_i \times r \pmod{q}$ 。
$b_1,b_2,...b_n$ $\sum_{i=1}^{n} b_{i}c_{i} \pmod{q}$ $c=c_1c_2....c_n$ 。
Bob 发现自己并不会还原，于是向你求助。

Day 5 T1

我们定义仙人掌为任何一条边至多在一个简单环内的简单连通图。
$n$ $f(l,r)$ $[l,r]$ 之间的点的时候，形成的连通块数量。你需要求出下面这个式子：
$\sum_{i=1}^n\sum_{j=i}^n f^k(i,j)$
$10^9+9$ $1\leq n\leq 200000,k\in\{1,2\}$ 。

$k=1$ $l\in [a,b],r\in[c,d]$ $[l,r]$ 的形式，可以用 set 预处理出来。

$k=2$ $[l,r]$ $k=1$ $O(n\log{n})$ 。

Day 5 T2

这是一道构造题。
$n$ $k$ $n$ $k$ $k$ $2\leqslant k\leqslant 10,2k+1\leqslant n\leqslant 1000$ 。

$k$ $a$ $b=n-a$ $k+1$ $ak+\frac 12 (b(k+1)-ak)$ ，求这个函数的最小值即可。构造方案由于 Erdős–Gallai 定理而必定存在。

Havel–Hakimi 算法 $(d_1,d_2,\cdots,d_n)$ $(d_2-1,d_3-1,\cdots,d_{d_1+1}-1,d_{d_1+2},d_{d_1+3},\cdots,d_n)$ 可简单图化，即可递归构造。

Erdős–Gallai 定理 $d$ $\sum d$ 是偶数且

\forall k\in[1,n],\sum_{i=1}^kd_i≤k(k−1)+\sum_{i=k+1}^n\min(d_i,k)

$ak$ 条边尽可能平均分配后，上面那个构造必然是有解的。（即我最早写的贪心其实是正确的，但毕竟后来用 dp 水过去了嘛）。

Day 5 T3

$B$ $x=\sum x_iB^i$ $r(x)$ 如下：
$r(x)=\begin{cases}x&x<B\\\sum\limits_{i=1}x_i&x\ge B\end{cases}$
$r(abcd_{16})=r(2e_{16})=r(10_{16})=1_{16}$ 。
$n$ $B$ $s$ $A$ $x$ $s[l\ldots r]$ $A$ $x$ $1\leq n,m\leq 2^{19},2\leq B\leq 16,0\leq x< B$ 。

$r(x)=x\bmod (B-1)$ $r(x)=0$ $r(x)=B-1$ $0$ $r(x)=0$ ，这个情况可以单独处理，我们忽略。

$\bmod (B-1)$ $O(B\cdot 2^{B})$ $r$ $l$ $B$ $s_{r,i,j}$ $r$ $i$ $j$ $r$ $s_{r,i}$ $O(nB^2)$ 的。

统计完区间，我们直接高维前缀和一下便能快速回答答案了。