【ECFINAL2019热身赛】B题

· · 个人记录

cnblogs地址：https://www.cnblogs.com/cdcq/p/12046012.html
原题：

给你一个长度为1e5的序列ai，问你它的所有子序列的最大值与最小值之差的1000次方的和是多少

即 \sum_{\text{p是a的子序列}} (max\{p\}-min\{p\})^{1000}

这题难点在于(max-min)^{1000}这个东西外边套了次方，不太好处理

首先需要注意一点的性质是因为只考虑最大值和最小值，所以考虑子序列实际上是考虑集合的子集

那么可以对原序列排序，然后枚举两个端点，对应区间的包含端点的所有子集就是最大值和最小值分别为端点的子集

即此区间对答案的贡献为 ((a_j-a_i)\cdot2^{j-i-1})^{1000}

接下来处理 (max-min)^{1000}

一个想法是差分转差为和，然而并没有什么卵子用

另一个想法是枚举区间时不枚举端点，而是枚举长度，这样可以把2的次幂提出来

但是仍旧无法把 (max-min)^{1000} 展开

最后的做法是暴力把上式展开，或者手玩小数据，可以发现规律

（涉及到区间问题时常用的一个思路是固定一个端点，考虑与另一个端点有关的变化情况）

所有左端点为1的区间的贡献和为

\sum((a_j-a_1)\cdot2^{j-2})^{1000} =2^{1000}\cdot(a_2-a_1)^{1000}+2^{1001}\cdot(a_3-a_1)^{1000}+...+2^{1000+n-1}\cdot(a_n-a_1)^{1000} =2^{1000}\cdot((a_2-a_1)^{1000}+2\cdot(a_3-a_1)^{1000}+...+2^{n-1}\cdot(a_n-a_1)^{1000})

把 2^{1000} 提出来，令 S=(a_2-a_1)^{1000}+2\cdot(a_3-a_1)^{1000}+...+2^{n-1}\cdot(a_n-a_1)^{1000}

暴力展开1000次方

=(a_2^{1000}+1000\cdot a_2^{999}\cdot a_1+...+a_1^{1000})+2\cdot(a_3^{1000}+...+a_1^{1000})+...+2^{n-1}\cdot(a_n^{1000}+...+a_1^{1000})

合并同次项

=a_2^{1000}+2\cdot a_3^{1000}+4\cdot a_4^{1000}+...+2^{n-1}\cdot a_n^{1000}) -1000\cdot a_1\cdot(a_2^{999}+2\cdot a_3^{999}+4\cdot a_4^{999}+...+2^{n-1}\cdot a_n^{999}) +C_{1000}^{2}\cdot a_1^2\cdot (...) ... +a_1^{1000}\cdot(1+2+4+...+2^{n-1})

发现规律了木有！

随着右端点下标增加，同次项的系数每次乘2

而 a_j^0,\ a_j^1,\ a_j^2,\ ...,\ a_j^{1000} 可以预处理

那么如果从左往右枚举左端点 i ， (a_{i+1}^k+2\cdot a_{i+2}^k+...+2^p\cdot a_n^k) 可以快速由 (a_{i+2}^k+...+2^{p-1}\cdot a_n^k) 乘 2 再 +a_{i+1}^k 得到

耗时1e5*1e3，有点紧，要善用递推性质，盲目龟速乘会挂 还需要注意的一个问题是序列中的相同元素 实际上手玩小数据或者直接证明都可以发现，相同的数按照上述方法处理仍然能得到正确的结果 这个留给读者证明233