Codeforces Round #177 (Div. 1 + Div. 2)

显然为了让结果尽量大，所以异或和应该和加法和接近。
观察样例可知，结果为n(n+1)，所以可猜测对于任意的n可构造出异或和n(n+1)的序列，即异或不存在两个1相消。
xjb证明：对于n来说，假设二进制最高位为p，则\(2^{p + 1} - 1 \oplus n\) 显然小于n；对于n-1来说(假设二进制最高位不变)，\(2^{p+1}-1 \oplus n - 1\)会大于\(2^{p+1} - 1 \oplus n\)。也就是\([2^{p + 1}-1 \oplus n, n]\)构成一个我们要的区间，而\([1,2^{p + 1}-1 \oplus n)\)则变成一个子问题。

因为\(l,r\)没有前导0，即最后的幸运数字长度均为\(|l|,|r|\)。
将问题看成求\([1,n]\)内\(a_1a_2+a_2a_3+…+a_{n-1}a_n\)的值。
长度为1时，幸运数字有4,7；
长度为2时，幸运数字有44,47,74,77;
记长度为\(l\)时，幸运数字有\(a_{1}^{l},a_{2}^{l},…,a_{n}^{l}\)，那么长度为\(l+1\)时，新的幸运数字为\(\overline{a_{1}^{l}4},\overline{a_{1}^{l}7},\overline{a_{2}^{l}4},\overline{a_{2}^{l}7}…,\overline{a_{n}^{l}4},\overline{a_{n}^{l}7}\)。此时是不考虑有上界的情况，有上界的情况时，最大值是前缀，且添加4、7时要根据下一位的值考虑，下一位是4时，最大值只能加4得到新的幸运数字，下一位是7时则相当于没有限制。
假设\(F_i=\sum_{i=1}^{K_i-1}{a_ia_{i+1}}\)，\(K_i\)表示幸运数字的个数。
当\(时s_{i+1}=4时\)\[F_{i+1}=\sum_{i=1}^{K_{i+1}-1}{A_iA_{i+1}}\\=\sum_{i=1}^{K_i-1}{\overline{a_i4}\cdot\overline{a_i7}}+\sum_{i=1}^{K_i-1}{\overline{a_i7}\cdot\overline{a_{i+1}4}}\\=\sum_{i=1}^{K_i-1}{(100a_i^2+110a_i+28)}+\sum_{i=1}^{K_i-1}{(100a_ia_{i+1}+40a_i+70a_{i+1}+28)}\\=100\sum_{i=1}^{K_i-1}{a_ia_{i+1}}+100\sum_{i=1}^{K_i-1}{a_i^2}+220\sum_{i=1}^{K_i-1}{a_i}+70(a_{K_i}-a_1)+56(K_i-1)\]
当\(s_{i+1}=7\)时，只需要加上\(\overline{a_{K_i}7}\)这项即可。
为了得到\(F_i\)，需要维护和、平方和，两个值推导与上面的类似。

巴特西