「517模拟赛1」ABC难题

Tips: 模数是$10^8+7$

不妨令序列总长为$n$，包含$m$种不同的数字

发现存在$ABC$的子序列只需要满足最左边的$A$和最右边的$C$之间有一个$B$

由于可能出现多个$ABC$，考虑计算不存在$ABC$的情况

那么可以枚举最左边的$A$和最右边的$C$分别为$X,Y$，那么需要不存在$ABC$，并且枚举的$X,Y$合法 的充要条件是

$[1,X-1]$中不存在$A$，$[X+1,Y-1]$中不存在$B$，$[Y+1,n]$中不存在$C$

这三个限制，每一个限制会让一种颜色能够选择的字母数量-1

那么枚举$X$，扫描每一个$Y$(注意不一定满足$X< Y$)，同时记录每个数字是否出现在$[1,X-1],[X+1,Y-1],[Y+1,n]$中

在每次扫描时改变限制，同步统计出受到$0,1,2,3$个限制的数字的个数，然后答案就是$(3-i)^k$之积

然而这样还不够，因为可能根本不存在$A,C$，不存在$A$或者$C$的答案为$2^m$，同时不存在$A,C$的答案为$1^m$，容斥一下即可