T1

100%

因为 $b$ 和 $d$ 都是正数，所以两边同时乘上 $b\times d$ 后中间的符号不变。

所以只需要比较 $a\times d$ 和 $b\times c$ 的关系，如果 $a\times d>b\times c$ 输出 >，如果 $a\times d<b\times c$ 输出 <，如果 $a\times d=b\times c$ 输出 =。

时间复杂度 $O(1)$。

T2

60%

从 $1$ 开始从小到大枚举整数 $x$ ，找到最大的 $x$ 满足 $x^2\leq N$，答案即为 $x^2$。

时间复杂度 $O(\sqrt{N})$。

100%

满足 $x^2\leq N$ 的最大整数 $x$ 实际上就是 $\lfloor \sqrt{N}\rfloor$。

如果使用 $\text{sqrt}$ 函数来求 $\lfloor \sqrt{N}\rfloor$，会因为精度误差而出错，比如 $\text{sqrt}(999999999999999999)$ 会被计算为 $1000000000$。

所以要使用精度更高的 $\text{sqrtl}$ 函数来计算。

计算 $x=\text{sqrtl}(N)$，答案即为 $x^2$。

注意：$\text{sqrtl}$ 函数的返回值是实数类型的，将其赋值给一个 $\text{long\ long}$ 类型的变量可以实现向下取整的效果。

时间复杂度 $O(1)$。

T3

100%

在字符矩阵中，从外到内的第 $i$ 层正方形，四条边对应的格子分别是：

• 第 $i$ 行的第 $i$ 列到第 $n+1-i$ 列；
• 第 $n+1-i$ 行的第 $i$ 列到第 $n+1-i$ 列；
• 第 $i$ 列的第 $i$ 行到第 $n+1-i$ 行；
• 第 $n+1-i$ 列的第 $i$ 行到第 $n+1-i$ 行。

从 $1$ 到 $\lceil \frac{n}{2}\rceil$ 枚举 $i$，当 $i$ 是奇数时将第 $i$ 层正方形的四条边对应的格子赋值为 #；当 $i$ 是偶数时将第 $i$ 层正方形的四条边对应的格子赋值为空格。

完成所有赋值后再输出字符矩阵即可。

时间复杂度 $O(n^2)$。

T4

20%

记最终合成白球的不同合成方案数量为 $answ$，最终合成黑球的不同合成方案数量为 $ansb$。

用 $\text{DFS}$ 枚举每一轮合成选择的两个球的位置，共有 $(n-1)!$ 种不同的位置选择方案。

每轮选好位置后，根据合成前这两个球的颜色，枚举合成的新球的颜色，继续 $\text{DFS}$ 枚举剩下球的合成。

最终如果合成为一个白球则 $answ$ 增加一，合成为一个黑球则 $ansb$ 增加一。

时间复杂度 $O((n-1)!2^n)$。

40%

对于测试点#3~4，因为所有球都是白球，所以每轮合成的新球的颜色一定为白色，最终一定合成为一个白球。

此时不同合成方案之间仅有每轮合成选择的两个球的位置不同，答案即为 $answ=(n-1)!$，$ansb=0$。

注意取模。

时间复杂度 $O(n)$。

结合第一部分可以拿到 $40\%$ 的分数。

100%

定义 $dp[l][r][0]$ 为将第 $l\sim r$ 个球合成为一个白球的不同合成方案数量，$dp[l][r][1]$ 为将第 $l\sim r$ 个球合成为一个黑球的不同合成方案数量。

考虑将第 $l\sim r$ 个球合成为一个球的最后一轮合成，本轮合成选择的两个球分别是第 $l\sim i$ 个球合成出的球（称为球 $A$）与第 $i+1\sim r$ 个球合成出的球（称为球 $B$），那么本轮合成的新球的颜色与球 $A$ 和球 $B$ 的颜色有关，且球 $A$ 的合成方案与球 $B$ 的合成方案是独立的，合成球 $A$ 所用的 $i-l$ 轮合成与合成球 $B$ 所用的 $r-(i+1)$ 轮合成的相对顺序也是独立的。所以将第 $l\sim r$ 个球合成为一个球的过程中，除最后一轮合成外剩下 $r-l-1$ 轮合成中，选择合成球 $A$ 的 $i-l$ 轮合成的位置有 $\text{C}_{r-l-1}^{i-l}$ 种选法。

用杨辉三角法预处理所有 $0\leq i\leq n$ 且 $0\leq j\leq i$ 的组合数 $\text{C}_i^j$。

如果第 $i$ 个球为白色，那么 $dp[i][i][0]=1,dp[i][i][1]=0$；如果第 $i$ 个球为黑色，那么 $dp[i][i][0]=0,dp[i][i][1]=1$。

对于 $l<r$ 的情况，用三重循环进行区间DP：

• 第一重循环从 $2$ 开始枚举区间长度 $len$；
• 第二重循环枚举区间的左端点 $l$，此时区间的右端点 $r=l+len-1$；
• 第三重循环在 $l\sim r-1$ 中枚举 $i$ 表示将第 $l\sim r$ 个球合成为一个球的最后一轮合成选择的两个球分别是第 $l\sim i$ 个球合成出的球 $A$ 与第 $i+1\sim r$ 个球合成出的球 $B$；
• 这种情况下，除最后一轮合成外剩下 $r-l-1$ 轮合成中，选择合成球 $A$ 的 $i-l$ 轮合成的位置有 $\text{C}_{r-l-1}^{i-l}$ 种选法；
• 如果球 $A$ 和球 $B$ 颜色相同，以都是白色为例：最终只能合成出白球，球 $A$ 的合成方案有 $dp[l][i][0]$ 种，球 $B$ 的合成方案有 $dp[i+1][r][0]$ 种，合成对应的转移为 $dp[l][r][0]+=dp[l][i][0]\times dp[i+1][r][0]\times \text{C}_{r-l-1}^{i-l}$；
• 如果球 $A$ 和球 $B$ 颜色不同，以球 $A$ 为白色且球 $B$ 为黑色为例：可以选择最终合成出黑球或白球，球 $A$ 的合成方案有 $dp[l][i][0]$ 种，球 $B$ 的合成方案有 $dp[i+1][r][1]$ 种，合成对应的转移为 $dp[l][r][0]+=dp[l][i][0]\times dp[i+1][r][1]\times \text{C}_{r-l-1}^{i-l}$ 以及 $dp[l][r][1]+=dp[l][i][0]\times dp[i+1][r][1]\times \text{C}_{r-l-1}^{i-l}$。

答案即为 $answ=dp[1][n][0]$，$ansb=dp[1][n][1]$。

时间复杂度 $O(n^3)$。

T5

20%

用 $\text{DFS}$ 枚举知识点的 $n!$ 种学习顺序，对于每种顺序判断是否为合法的学习方案，每当找到一种的学习方案，让答案增加一。

时间复杂度 $O(n!n)$。

60%

因为每个知识点最多只会有一个前置知识点，可以把这类前置关系看成树的结构，$p_i$ 是 $i$ 的父节点。

用 $dp[i]$ 表示只考虑以 $i$ 为根的子树内的知识点时，合法的学习方案的数量。记 $siz[i]$ 为以 $i$ 为根的子树内的知识点的数量。

考虑知识点 $x$ 有 $m$ 个子节点，分别是 $y_1,y_2,\dots,y_m$ 的情况下，如何计算 $dp[x]$。

$x$ 一定是第一个学习的知识点。对于以 $x$ 的不同子节点为根的各子树，每个子树的知识点对应的合法学习方案独立，不同子树的知识点的相对学习顺序也是独立的：

• 以 $y_1$ 为根的子树，有 $siz[y_1]$ 个知识点需要学习，即需要从 $siz[x]-1$ 个剩余的位置中，选出 $siz[y_1]$ 个位置给子树 $y_1$ 学习，这 $siz[y_1]$ 个知识点对应的合法学习方案为 $dp[y_1]$，共有 $\text{C}_{siz[x]-1}^{siz[y_1]}\times dp[y_1]$ 种情况；
• 以 $y_1$ 为根的子树，有 $siz[y_2]$ 个知识点需要学习，即需要从 $siz[x]-1-siz[y_1]$ 个剩余的位置中，选出 $siz[y_2]$ 个位置给子树 $y_2$ 学习，这 $siz[y_2]$ 个知识点对应的合法学习方案为 $dp[y_2]$，共有 $\text{C}_{siz[x]-1-siz[y_1]}^{siz[y_2]}\times dp[y_2]$ 种情况；
• 以此类推，以 $y_i$ 为根的子树，有 $siz[y_i]$ 个知识点需要学习，即需要从 $siz[x]-1-\sum_{j=1}^{i-1}siz[y_j]$ 个剩余的位置中，选出 $siz[y_i]$ 个位置给子树 $y_i$ 学习，这 $siz[y_i]$ 个知识点对应的合法学习方案为 $dp[y_i]$，共有 $\text{C}_{siz[x]-1-\sum_{j=1}^{i-1}siz[j]}^{siz[y_i]}\times dp[y_i]$ 种情况；
• 所以 $dp[x]=\prod_{i=1}^{m}(\text{C}_{siz[x]-1-\sum_{j=1}^{i-1}siz[y_j]}^{siz[y_i]}\times dp[y_i])$。

用杨辉三角法预处理所有 $0\leq i\leq n$ 且 $0\leq j\leq i$ 的组合数 $\text{C}_i^j$。

先进行第一次 $\text{DFS}$ 计算出 $siz$ 数组。

再进行第二次 $\text{DFS}$ 计算 $dp$ 数组：

• 初值为 $dp[x]=1$；
• 枚举 $x$ 的子节点，当枚举到 $x$ 的第 $i$ 个子节点 $y_i$ 时，维护 $num=siz[x]-1-\sum_{j=1}^{i-1}siz[y_j]$，转移为 $dp[x]=dp[x]\times(\text{C}_{num}^{y_i}\times dp[y_i])$。

由于可能存在多个 $p_i=0$ 的知识点，可以把 $0$ 看成树的根，从 $0$ 出发进行 $\text{DFS}$，答案就是 $dp[0]$。

算法的时间复杂度瓶颈在于用杨辉三角法预处理组合数。

注意：三个或更多的数相乘可能会超出 $\text{long\ long}$ 范围，要及时取模。

时间复杂度 $O(n^2)$。

100%

预处理模意义下阶乘 $fac[i]=i!$ 和模意义下阶乘的逆元 $ifac[i]=\frac{1}{i!}$。过程中只需要在求 $ifac[n]$ 时计算一次逆元。关于模意义下的逆元问题请同学们自行查阅资料。

在第二部分的基础上，将组合数的计算方式改为 $\text{C}_i^j=\frac{i!}{j!\times (i-j)!}=fac[i]\times ifac[j]\times ifac[i-j]$。

时间复杂度 $O(n)$。

T6

10%

对于每个询问，对 $x_i$ 依次进行第 $L_i\sim R_i$ 个修改即可。

注意取模。

时间复杂度 $O(mn)$。

30%

对于测试点#2~3，因为 $a_i=0$，所以不论对 $x_i$ 依次进行第 $L_i\sim R_i-1$ 个修改后的结果是多少，都会将结果乘上 $a_{R_i}=0$ 再加上 $b_{R_i}$。

因此第 $i$ 个询问的答案为 $b_{R_i}$。

时间复杂度 $O(n+m)$。

结合第一部分可以拿到 $30\%$ 的分数。

50%

对于测试点#4~5，因为 $b_i=0$，所以对 $x$ 进行第 $i$ 个修改也就是令 $x=x\times a_i$。

因此第 $i$ 个询问的答案为 $x_i\times \prod_{j=L_i}^{R_i} a_j$。

乘法具有结合律：计算三个整数相乘时，先把前两个数相乘，再和另外一个数相乘，或先把后两个数相乘，再和另外一个数相乘，结果不变。乘法的结合律可以推广到多个整数相乘的情况。

预处理 $a_i$ 的前缀乘积 $f[i]=\prod_{j=1}^{i} a_j$，以及模意义下 $f[i]$ 的逆元 $g[i]=\frac{1}{f[i]}$。其中 $g[0]=1$。

第 $i$ 个询问的答案为 $x_i\times f[R_i]\times g[L_i-1]$。

注意：三个或更多的数相乘可能会超出 $\text{long\ long}$ 范围，要及时取模。

时间复杂度 $O(n+m)$。

结合第一、第二部分可以拿到 $50\%$ 的分数。

100%

考虑对 $x$ 先进行参数为 $c$ 和 $d$ 的修改，再进行参数为 $e$ 和 $f$ 的修改，结果为 $e\times(c\times x+d)+f=e\times c\times x+e\times d+f$。

也就是说，可以把先进行参数为 $c$ 和 $d$ 的修改再进行参数为 $e$ 和 $f$ 的修改的情况，合并为进行一个参数为 $e\times c$ 和 $e\times d+f$ 的新修改。

并且修改也具有结合律：依次进行三个修改时，先把前两个修改合并，再与另外一个修改合并，或先把后两个修改合并，再与另外一个修改合并，只要保证合并时修改间的相对位置不变，结果不变。修改的结合律也可以推广到多个修改依次进行的情况。

因此我们用线段树维护区间内修改依次合并出的新修改，可以用结构体来保存：$tre[i]$ 保存线段树上节点 $i$ 对应的区间内的修改依次合并出的新修改，其中 $tre[i].a$ 表示这个新修改的参数 $a$，$tre[i].b$ 表示这个新修改的参数 $b$。

用 $ask(x,L,R)$ 表示第 $L\sim R$ 个修改依次合并出的新修改，$ask$ 函数的返回值为结构体。

对于第 $i$ 个询问，计算 $ans=ask(L_i,R_i)$，答案为 $ans.a\times x_i+ans.b$。

时间复杂度 $O(n+m\log(n))$。