AtCoder
数学,贪心
显然 \(C_i\) 越小的位越早被修改越好。所以我们将 \(C_i\) 从小到大排序。对于任意的 \(S\),答案都是一样的。我们依次考虑 \(S\) 和 \(T\) 的每一位是否相同。设我们考虑到第 \(i\) 位。
若相同,则这一位对答案的贡献为 \(0\)。
若不同,则根据上面的贪心,第 \(i\) 位之前的位置已被修改完毕。所以在 \(T\) 中第 \(i\) 位之前的位置可以任意选数,对第 \(i\) 位的贡献不影响。
对于第 \(i\) 位之后的位置,我们枚举有多少个不相同的位置。
则答案为:
\(2^n\left(\sum\limits_{i=1}^n2^{i-1}\cdot C_i\cdot\sum\limits_{j=0}^{n-i}\dbinom{n-i}{j}(j+1)\right)\)
考虑化简:
\(\sum\limits_{j=0}^{n-i}\dbinom{n-i}{j}(j+1)=\sum\limits_{j=0}^{n-i}\dbinom{n-1}{j}+\sum\limits_{j=0}^{n-i}\dbinom{n-i}{j}j=2^{n-i}+\sum\limits_{j=0}^{n-i}\dbinom{n-i}{j}j\)
考虑吸收恒等式:
\(∵\begin{aligned}\dfrac{r}{k}\dbinom{r-1}{k-1}&=\dfrac{r}{k}\times \dfrac{(r-1)^{\underline{k-1}}}{(k-1)!}=\dbinom{r}{k}\end{aligned}\)
\(∴r\dbinom{r-1}{k-1}=k\dbinom{r}{k}\)
即
\(\begin{aligned}2^{n-i}+\sum_{j=0}^{n-i} \dbinom{n-i}{j}j =2^{n-i}+\sum_{j=0}^{n-i}\dbinom{n-i-1}{j-1}(n-i)=2^{n-i}+(n-i)\sum_{j=0}^{n-i-1}\dbinom{n-i-1}{j}=2^{n-i}+(n-i)2^{n-i-1}\end{aligned}\)
已完成
手机扫一扫
移动阅读更方便
你可能感兴趣的文章