T1
$dp[i]=max(dp[j]-C_{j+1}^{2}+ij+a[i]-C_i^2)$
简单的一个线段树维护凸包
T2
设$dp[S][i]$代表$[1,k]$选的次数为$S$，上一次选i的之后的方案数
要求第$k$小的字典串，逐位选择后用$dp$数组来判断是否小于等于$k$
期望得分$80$分
$k<=26,n<=2e18$
发现其实k>8则每次一定是加一定形如$ABABABABA$的前缀使得$k-=2$
T3
不妨让$n=n-k+m,k=m$
现在就和$m$无关了
设$f(n,k)$代表$n,k$时的答案
假设$B[i][m]!=B[i+1][m]$
设$B[i][m]=x$
则$B[i][m+1...k]$一定是$n$的后缀,$B[i+1][m+1...k]$一定是$x+2,x+3...x+k$
($k=1$时不满足)
差值为$n-x-k$,那么总贡献即为
$$sumlimits_{i=1}^{n-k}n-k-i$$
$$=C_{n-k}^{2}$$
$$=g(n,k)$$
如果$B[i][m]=B[i+1][m]$,贡献是$f(n-x,k-1)$
综上所述:$f(n,k)=g(n,k)+sumlimits_{i=1}{n-k+1}f(n-i,k-1)$
现在问题转化为对于每个$g(n,k)$求出它的贡献系数来
从实际含义入手考虑这个式子，相当于把$n$拆成$k$个正整数
那么$g(x,y)$的系数就是$n-x$拆成$k-y$个正整数的方案数
考虑枚举$y$求出所有$x$的答案之和$(y<=x<=n)$
其实就是把$n-y$拆成$x-y$和$n-x$，并且在前面选三个，在后面选$k-y$个
总的即是$C_{n-y}^{k-y+3}$