考虑任意时刻区间均为奇数的情况
观察到一个区间被取到的概率与区间外的具体状态无关，只与区间外取了多少次有关，因此考虑计算一个区间被选中后的出现次数，设 \(dp_{[l,r],t}\) 表示区间 \([l,r]\) 在剩余 \(t\) 次入座时被选中的最终所有状态的出现次数之和，贡献加入中点 \(ans_{mid}\)，最终的答案就是 \(\cfrac{ans_i}{n^{\underline{m}}}\)
这个状态数显然是 \(O(n)\) 的，因为在区间内选取一个位置分裂后的两边区间是本质相同的，只需要转移一边然后复制一下
对于一个区间到其子区间的转移，有：
\[dp_{[l,mid-1],i}=\sum\limits_{t>i}\binom{t-1}{i}(r-l+1)(r-mid)^{\underline{t-i-1}}dp_{[l,r],t} \]其中 \(r-l+1\) 是选到区间内的方案数，\((r-mid)^{\underline{t-i-1}}\) 是另一个区间 \([mid+1,r]\) 选取的贡献，并且需要带一个组合系数
对于区间转移到答案，有：
\[ans_{mid}=\sum\limits_{t=1}^{r-l+1}(r-l+1)^{\underline t}dp_{[l,r],t} \]通过在初始时将答案 \(\times m!\)，可以将下降幂变成组合数进行减法卷积
对于偶数长度的区间，只需要将贡献取半分别加入两个中点，分析一下状态数仍然是 \(O(n)\) 的，最终复杂度 \(O(n\log n)\)，常数巨大
标签：Solitude,mid,Hello,ans,区间,underline,dp From： https://www.cnblogs.com/pidan123/p/17757223.html