数数与dp
CF294C Shaass and Lights
记被分成的 \(m+1\) 段每一段的长度为 \(l_i\)
答案为
\[\frac{(n-m)!}{\prod\limits_{i=1}^{m+1}l_i!}\times \prod\limits_{i=1}^{m+1}2^{l_i-1}
\]
前面是不同段之间的顺序打乱，后面是每一段中前 \(l_i-1\) 个操作各有 \(2\) 个选择
CF1753C Wish I Knew How to Sort
先数有几个 \(0\) 记为 \(cnt\)
在数前 \(cnt\) 个有几个 \(1\) 记为 \(tot\)
答案为
\[\sum\limits_{i=1}^{tot}\frac{n(n-1)}{2i^2}
\]
即对于每一对有 \(\frac{n(n-1)}{2}\) 操作，其中有 \(i^2\) 对操作是有效的，即从 \([1,cnt]\) 选一个 \(1\) 与一个 \([cnt+1,n]\) 选一个 \(0\) 交换
CF1657E Star MST
dp[i][j] 表示考虑到第 \(i\) 个点，目前和 \(1\) 相连的最长的边为 \(j\) 的方案数
令 \(sum_{i,j}=\sum\limits_{k=1}^j{dp_{i,k}}\)
\[dp_{i,j}=\sum\limits_{t=1}^{i-1}sum_{t,j-1}\binom{n-t}{i-t}(k-j+1)^{\frac{(i+t-3)(i-t)}{2}}
\]
CF660E Different Subsets For All Tuples
经典套路，转化为求每个可能的串的贡献
发现对于长度相同的串，贡献是一样的，所以考虑怎么求一个定长的串的贡献
设当前考虑的串长为 \(k\) , 最后一个字符的位置为 \(j\)
选择哪些是子串内的有 \(\binom{j-1}{k-1}\) 种方案， \(j\) 之前每个非子串内的字符有 \(m-1\) 种选择，因为不能提前选到下一个字符，\(j\) 之后的字符每个有 \(m\) 种选择
所以总共有
\[\sum\limits_{k=1}^{n}m^k\sum\limits_{j=k}^n\binom{j-1}{k-1}(m-1)^{j-k}m^{k-1} = \sum\limits_{j=0}^{n-1}\sum_{k=0}^jm^{n-j}m^k(m-1)^{j-k}\binom{j}{k}
\]
注意到 \(m^k(m-1)^{j-k}\) 是二项式形式，所以原式为
\[\sum\limits_{j=0}^{n-1}m^{n-j}(2m-1)^j
\]
暴力计算即可
p.s. 好像最后是个卷积可以FFT?