没一眼看出来还是拉了。
考虑区间 dp，\(f_{i,l,r}\) 表示 \([l,r]\) 前 \((i-1)\) 位都相同，看后面 \([i,n]\) 位填数使得递增的方案数是多少。
这样已经可以做了，但是还不够，要追求一下最简单的写法。想想，发现每次 dp 是要分为多个儿子乘起来，内部还要搞个 dp。但可以改成每次两个儿子乘起来的方式，那就是 \(f_{i,l,r,k}\)，\(k\) 表示第 \(i\) 位要填 \(\geq k\)，其余含义仍不变。
这样子就枚举 \(k\) 填了哪个前缀，时间复杂度是 \(\mathcal{O}(n^4|\Sigma|)\)，采用记忆化搜索的写法。
标签：Count,题解,Strictly,Increasing,ABC292G,dp From： https://www.cnblogs.com/do-while-true/p/17445758.html