分开考虑 ${1,2,…,n}$ 的贡献，对于数字 $k$ ，以 $k$ 为最小值的行有 $C_{n^2-k}^{n-1}$ 种。

这一行可以是 $[1,n]$ 中任意一行，外加剩下的 $n^2-n$ 个数字可以随意排列，以及这一行内部可以随意排列，因此包含某个 $a_i=k$ 的布局方法有 $C_{n^2-k}^{n-1}\times C_n^1\times (n^2-n)!\times n!$ 种。

讲一下大致的，题意细节很多，建议自己读一下结合理解……

可以结合题面那张图来理解

给定一种由三个部件组成的加密方式

• 第一个部件由多对 $(s_i,t_i)$ 组成，会将输入的字符 $s_i$ 和 $t_i$ 互转

• 第二个部件由多行字符串 $p_i$ 组成，其中每个 $p_i$ 是一个26个字母的排列，并且每个 $p_i$ 还带有一个初始时正序的排列 $q_i=abcd…xyz$，每次转化会先用上次转化后字符的下标 $idx$ ，去获取 $ch=q_i[idx]$ ，然后在 $p_i$ 中找到 $ch$ 的位置 $idx$，再去做下一次转化

  • 第一次转化时用传入字符的字典序做下标，比如传入 $Z$，则一开始 $idx=26$
• 第三个部件类似第二个部件，细节有点差别

给定输入字符串，输出加密后的字符串

给一个 $N$ 点的树，要求删掉任意数量的点使得剩下的联通块大小均 $\ge2$，问有多少种删点方式

称那些没有边相连的点为独立点

考虑子树 $i$，有三种状态：

• 根没有被删除且根不为独立点，有 $f_i$ 种方案
• 根没有被删除且根为独立点，有 $g_i$ 种方案
• 根被删除，有 $h_i$ 种方案

考虑转移：

• 转移时，如果根不被删，那只有所有子树都删根，根才会为独立点，否则根不为独立点

$$f_i=\prod\limits_{j}(f_j+g_j+h_j) - \prod\limits_{j}h_j \\ g_i=\prod\limits_{j}h_j$$

• 如果根被删，则子树的 $g_j$ 无法转移上来

$$f_i=\prod\limits_{j}(f_j+h_j)$$

给一个长度 $n$ 的数组，$m$ 次操作，操作有两种：

• 对于区间 $[L,R]$， $a_i+=lowbit(a_i)$
• 求 $[L, R]$ 的区间和，对 998244353 取模

数据范围 $T\le 20, n\le 10^5, m\le 10^5$

对于一个数 $a_i$，最多进行 $log$ 次1操作后，再对 $a_i$ 进行1操作则等价于 $a_i=a_i\times 2$，称这样的 $a_i$ 为稳定态

因此对线段树上每个节点 $seg_k$ 维护一个 $bool_k$，表示对于 $k$ 所代表的区间$[L_k,R_k]$，是否所有的 $a_i$ 均已处于稳定态，如果是，则直接对 $seg_k$ 做区间乘2。

否则就继续递归更新 $seg_{k\times2}$ 和$seg_{k\times 2+1}$。对于每个数，最多进行 $log$ 次1操作，有 $log$ 个区间覆盖它，总共 $n$ 个数。因此额外拆分的次数不会超过 $nlog^2$ 次

给定长度 $n$ 的斜坡，丢一个球在 $p$ 位置，如果 $p$ 位置为空，则该球将会留在 $p$ 位置。否则它会从 ${p-1,p-2,…,1}$ 找一个最近的空位置并留在该位置。如果 $[1,p]$ 全部不为空，则该球将会掉出斜坡。

一共要丢 $m$ 个球，用 ${p_1,p_2,…,p_m}(1\le p_i\le n)$ 表示一种丢球方案，询问有多少种方案能刚好掉出去 $k$ 个球。

数据范围 $T\le 1000, n\le 500, m\le 1000, 0\le k\le 500$

考虑斜坡最终的形状，一定会有一段全被球填满的前缀，因为球只有被丢在这种前缀上才能掉出斜坡。

我们设这段前缀长度为 $x$，而 $x+1$ 一定是空的，那么整段斜坡就被分成了左右两半：

• 左半边长度 $x$，填满了球，并且一共有 $x+k$ 个球丢在了上面
• 右半边长度 $n-1-x$，一共有 $m-x-k$ 个球丢在了上面，考虑到 $x+1$ 是空的，右半边就相当于 $m-x-k$ 个球丢在长度 $n-1-x$ 的斜坡上并且没有球掉出斜坡

我们用 $f_{ij}$ 表示 $j$ 个球丢在长度 $i$ 的斜坡上把斜坡填满的方案数，$g_{ij}$ 表示 $j$ 个球丢在长度 $i$ 的斜坡上没有球掉出去的方案数，则有答案

$$ans=\sum\limits_{x}f_{x,x+k}\times g_{n-1-x,m-x-k}\times C_m^{x+k}$$

接下来考虑求解 $f_{ij}$ 和 $g_{ij}$，求 $g_{ij}$ 的过程比较好理解，先来求 $g_{ij}$：

从左往右考虑，在第 $i$ 个位置放置 $k$ 个球，则有 $g_{ij}=g_{i-1,j-k}\times C_j^k$，控制一下枚举范围 $j\le i$。

解释一下这个 $C_j^k$，使用丢球序列 $p$ 来考虑，$g_{i-1,j-k}$ 相当于很多个长度为 $j-k$ 的合法序列，而 $f_{i,j}$ 则是往旧序列中插入 $k$ 个 $i$，相当于在长度 $j$ 的序列中选择 $k$ 个位置放 $i$，剩下位置用来排列 $g_{i-1,j-k}$。

再来求 $f_{ij}$：

$f_{ij}$ 关键在于从右向左考虑转移，在斜坡最左边新加一个位置，放置 $k$ 个球，则有 $f_{i,j}=f_{i-1,j-k}\times C_j^k$

之前看题解转移式一直以为 $f_{ij}$ 也是从左往右转移，但这样可能会出现当前出现了空的段但后面放了很多而填满了的情况，所以一直想不通。感谢@Nanako一句从右向左点醒我。