CF623E Transforming Sequence（多项式/倍增fft/动态规划)CF623E Transforming Sequence
CF623E Transforming Sequence经典的倍增NTT题目，但是由于万恶的模数导致这道题变成了倍增MTT要求n个数前缀或严格递增的序列个数，一共有k位。然后我们考虑进行dp，然后我的思路就是fi,jf_{i,j}fi,j表示前i位在k位中有j位的方案数，然后可以利用组合数进行转移，但是这个状态设计不优秀，主要在于它包含了这j位在k位中哪些位置的信息，但是我们完全不需要，因为这j位和其他j位是完全等价的，我们本质上只需要考虑这j位，那么得到另一个状态设计gi,jg_{i,j}g
