模拟赛（2022.10.24）

· · 个人记录

\texttt{总体记录}

比赛时间：2022-10-24 07:30:00 - 2022-10-24 11:30:00
比赛结果：100 + 20 + 100 + 0 = 220
比赛排名：rk1

\texttt{T1 三角阵}

--- 首先若是两个小三角形在同一个大三角形内，则直接将前缀忽略，直至不在同一三角形。 此时可以通过某些旋转和翻转让起点在 $\texttt{T}$，终点在 $\texttt{R}$。 然后可以算出起点达到它所在的大三角形的左下角和右下角的步数。 到达左下角的步数再加上大三角形边长即为到右下角大三角形左下角的步数。 此时就已经知道抵达右下角大三角形上侧和左侧的步数。 考虑终点在大三角形内的具体位置。 - 如果是 $\texttt{T}$，则左下角步数增加边长。 - 如果是 $\texttt{L}$，则上侧步数增加边长。 - 如果是 $\texttt{R}$，则两侧步数都增加边长。 然后递归下去即可，达到边界时取两者最小值。 # $\texttt{T2 matrix}

你可以在一个 n \times n 的矩阵的每个位置任意填 0,1,2。
求有多少个矩阵满足至少存在一行或一列所有位置填的数都相同，答案对 998244353 取模。

--- 可以记至少有 $i$ 行数相同，$j$ 列数相同的方案数为 $f(i,j)$。 由容斥大法得到： $$ans=\sum\limits_{i=0}^n\sum\limits_{j=0}^n[i+j>0](-1)^{i+j+1}\binom{n}{i}\binom{n}{j}f(i,j)$$ 考虑到： - $i=0$ 时，$f(0,j)=3^j \cdot 3^{n(n-j)}

所以需要求：

ans_0=\sum\limits_{i=1}^n\sum\limits_{j=1}^n(-1)^{i+j+1}\binom{n}{i}\binom{n}{j}f(i,j) =3\sum\limits_{i=1}^n\sum\limits_{j=1}^n(-1)^{i+j+1}\binom{n}{i}\binom{n}{j}3^{(n-i)(n-j)}

考虑转而枚举 n-i 和 n-j，于是：

=3\sum\limits_{i=0}^{n-1}\sum\limits_{j=0}^{n-1}(-1)^{i+j+1}\binom{n}{i}\binom{n}{j}3^{ij} =3\sum\limits_{i=0}^{n-1}(-1)^{i+1}\binom{n}{i}\sum\limits_{j=0}^{n-1}\binom{n}{j}(-3^i)^j

由二项式定理有：

\sum\limits_{j=0}^n\binom{n}{j}(-3^i)^j=(1+(-3^i))^n

于是得：

ans_0=3\sum\limits_{i=0}^{n-1}(-1)^{i+1}\binom{n}{i}\left[(1+(-3^i))^n-(-3^i)^n\right]

然后就可以求了。
最后把 i=0 或 j=0 且 i,j 不同时为 0 的贡献补上即可。

\texttt{T3 骨粉}

有 n 个数 t_i，每秒所有 t_i 会自然减去 1，每秒你可以选择一个 i 将 t_i 减去 x。如果 t_i \le 0 就说明其成熟。

$1 \le n,m \le 10^5,0 \le s_i \le 10^{18},1 \le x,t_i \le 10^{18},1 \le \sum t_i \le 10^{18}$。 --- 显然可以二分答案。 设二分的值为 $v$，第 $i$ 个数被减 $x$ 的次数为 $a_i$。 那么存在式子：$t_i-s-a_ix \le v$，则有 $a_i=\max\{\left\lceil \dfrac{t_i-s-v}{x} \right\rceil,0\}$。 二分应该 check 是否满足 $\sum\limits_{i=1}^n a_i=\sum\limits_{i=1}^n \max\{\left\lceil \dfrac{t_i-s-v}{x} \right\rceil,0\}\le s$。 继续分析题目性质，以下记 $k=s+v$。 $$\left\lceil \dfrac{t_i-k}{x} \right\rceil=\left\lceil \left([\dfrac{t_i}{x}]+\{\dfrac{t_i}{x}\}\right)-\left([\dfrac{k}{x}]+\{\dfrac{k}{x}\}\right)\right\rceil$$ $$=[\dfrac{t_i}{x}]-[\dfrac{k}{x}]+\left\lceil \{\dfrac{t_i}{x}\}-\{\dfrac{k}{x}\}\right\rceil$$ $$=[\dfrac{t_i}{x}]-[\dfrac{k}{x}]+\left[ \{\dfrac{t_i}{x}\}>\{\dfrac{k}{x}\}\right]$$ $$=[\dfrac{t_i}{x}]-[\dfrac{k}{x}]+\left[(t_i \bmod x)>(k \bmod x)\right]$$ 因此需要知道有多少个 $t_i > k$ 并且需要知道其中有多少个 $t_i$ 满足 $(t_i \bmod x)>(k \bmod x)$。 这些事情可以由离线+线段树或者主席树完成。 因此是 $O(n \lg v+m\lg^2 v)$ 的。 # $\texttt{T4 城市}

不会。