(题解由比赛出题人提供，点击右侧“本文相关内容”的题目即可开始做题）

T1 序列
考虑到类似于差分的思想。其实就是给出数字的取值，要这长度为n-1的序列所有数字的乘积是1。-2的个数必须是 偶数，0.5的个数和-2的个数相同，位置是任意的，于是可得答案为
时间复杂度O(n)。

T2 随机数
将随机数生成器运行x次产生奇数个1的概率记为f(x) 由独立性可知，f(a+b)=f(a)(1-f(b))+f(b)(1-f(a))=f(a)+f(b)-2f(a)f(b)
已知n的十进制表示，使用十进制下的快速幂可以计算f(n)。

T3 异或和
曼哈顿距离可以分解为X轴的距离和Y轴距离的和。分别考虑每一维对答案的贡献。用前缀和的方法处理即可。 时 间复杂度O(nm)。

T4 网格图
设dp状态为 表示在t时刻上一刻的移动为d时位置在(n,m)的方案数。转移的时候考虑下一时刻可能的移动 方式即可。 时间复杂度O(nmt)。

T5 极差
从左到右枚举右端点，用线段树维护每个左端点对应的价值。同时对每个序列分别用单调栈处理出每个左端点对应 的最大值和最小值的情况，于是线段树上需要维护三个序列（表示原有的三个序列固定右端点的区间极差，记为 a,b,c）的积之和，并支持对一个序列的一个区间同时加上一个数。 在线段树上分别维护1,a,b,c,ab,ac,bc,abc的区间 和，这时a,b,c中任意一个被加上一个数，都可以对应更新，例如a增加x，则更新a+=x,ab+=bx,ac+=cx,abc+=bcx，操 作满***换律和结合律，可以在线段树上打标记维护。 时间复杂度O(nlogn) 将原问题拓展到k个序列上，时间复杂 度为

T6 01串
可以使用可持久化AVL树（当然也可以用其它类似的数据结构）维护原序列，以分裂合并作为平衡树的基本操作， 原序列被存储在平衡树的叶子上。 每次操作1,2,3时可以先把序列按l,r分裂成三段，操作后再将三段合并恢复出序 列。 以下用+表示连接两个序列，:=表示赋值。 对操作1，设第二段为x，重复执行x := x+x，直到x已经被重复了超 过k次，再切掉多余的部分； 对操作2，设第二段为x，其翻转为y，重复执行x,y := x+y,y+x，直到x已经被按规则重 复了超过k次，再切掉多余的部分； 对操作3，只需把第二段置为空； 对操作4，维护1的个数，在树上自顶向下地 二分查找即可。 可持久化AVL树维护序列时，一次分裂操作（按给定位置将一个长度为x的序列分为两个）时间复 杂度为O(logx)，二分操作时间复杂度与分裂相同。 一次一般的合并操作的时间复杂度同样为O(logx)，但注意到在 操作1和操作2中的倍增过程中，合并的两个序列具有相同的树高，合并时只需新建一个点，左右孩子为被合并的两个点，时间复杂度为O(1)。 因此总的时间复杂度O(n+mlogM)，其中M为序列的最大长度。 空间复杂度与时间相 同，为O(n+mlogM)。

其他疑问可加以下交流群（加入一个即可啦~）
牛客多校算法训练营1：453799454
牛客全国算法训练营2：330766563
牛客多校算法训练营3：934889305