(T1)
听说DY讲过，但是咋就一点印象也没有捏
首先证明一下这道题的关键性质：
点燃一个战队后一个区间内的所有战队都会被引燃
假设(km,bm)代表最小能被直接引燃的战队
则有(bm<bx,km>kx)
假如存在一个(y(kx<ky<km))
讨论一下(b)的相对大小
(1>by<bm)
(y)以后一定会被(x)引燃
(2>bm<by<bx)
y以后一定会被(x)引燃
(3>by>bx)
(y)一定会被引燃后的(m)引燃
所以可以得出上述结论
现在问题变成了线段覆盖问题，用树状数组解决即可
(T2)
把问题转化到一个矩阵上
第一行是(T)，最后一行是(S)
中间是变化过程
从后往前扫一遍(T)
维护(f[i])代表(T[i]=S[f[i]])并且(f[i]<=f[i+1](i<n))的最大位置
那么再从后往前扫一遍(T)
维护一个(f[i])的队列(注意去重)
那么对于位置i而言
队列里有且仅有(fx>i)的(fx)
对答案的贡献便是队列的大小
(T3)
(f[i][j])代表一条链状态为i结尾为j的方案数 (f[i][0]=sum(f[i][j]))
(g[i][j])代表若干条链状态为i边数为j的方案数
(h[i])代表选(i)条边的方案数
(h^n)对应的第(i)项(*(n*k-i)!)便是至少(i)条边的方案数
(NTT)解决即可
(n)次方可以在点值的时候乘