概述
CF623E Transforming Sequence
经典的倍增NTT题目，但是由于万恶的模数导致这道题变成了倍增MTT
要求n个数前缀或严格递增的序列个数，一共有k位。
然后我们考虑进行dp，然后我的思路就是 f i , j f_{i,j} fi,j表示前i位在k位中有j位的方案数，然后可以利用组合数进行转移，但是这个状态设计不优秀，主要在于它包含了这j位在k位中哪些位置的信息，但是我们完全不需要，因为这j位和其他j位是完全等价的，我们本质上只需要考虑这j位，那么得到另一个状态设计 g i , j g_{i,j} gi,j表示前i个数一共j位都变成1的方案数，本质上 f i , j = ( k j ) g i , j f_{i,j}=binom{k}{j}g_{i,j} fi,j=(jk)gi,j
然后这时就有一个非常优秀的性质 g n + m , i = ∑ j = 1 i g n , j g m , i − j 2 j m g_{n+m,i}=sum_{j=1}^ig_{n,j}g_{m,i-j}2^{jm} gn+m,i=∑j=1ign,jgm,i−j2jm然后我们就可以进行分治MTT了QAQ
这个状态设计很巧妙，它不是直指答案的，而是将各个等价的独立子问题分开，这个思路非常巧妙，甚至我们对于这样的问题，即使无法用多项式优化，也可以将O(n)变为O(logn)
最后
以上就是醉熏花卷为你收集整理的CF623E Transforming Sequence（多项式/倍增fft/动态规划)CF623E Transforming Sequence的全部内容，希望文章能够帮你解决CF623E Transforming Sequence（多项式/倍增fft/动态规划)CF623E Transforming Sequence所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复