题目大意
有\(T\)组数据，每组数据给定两个\(l,n\in\mathbb{N*}\),构造一个长为\(l\),每个元素不超过\(n\)的数组
令他为\(a\),要使
最大，问最大值为多少
浅浅谈一下？
-
首先，我们肯定从那个式子入手，我们可以发现\(\sum_{i=1}^l\sum_{j=1}^{i-1}\)这个东西，就是让一个数组里的每两个元素一一异或
-
于是，问题就转变成了你需要构造一个\(a\)数组，里面的每两个元素一一异或的值加起来最大
-
我们继续转化，发现异或就是把每个数变成二进制，进行运算的，所以我们就可以想象有一堆二进制数，他们现在要一一异或
-
我们来认识一下异或:\(\oplus\)
-
运算规则
-
只要不一样就是\(1\),不一样就是\(0\)
-
例子：\(01_{(2)} \oplus 11_{(2)}=10_{(2)}\)
-
发现了什么？
-
只有两边各有一个\(0\)或\(1\)这一位才为\(1\)
-
我们再来认识一下位值
-
假设有一个\(101_{(2)}\),它的十进制是什么？
-
是不是\(4+1=5\)?所以第三位\(1\)它的值就是\(2^{3-1}=4\)
-
我们归纳一下，如果一个二进制数，它的第\(k\)位是1，那么那一位贡献的值就是\(2^{k-1}\)
-
好啦，以上就是前置芝士
回到本题
-
既然我们吧那个式子转换成一堆二进制一一异或，我们就可以每一位每一位的看
-
假如现在有\(l\)个二进制数，我们单独看看第\(k\)位
-
假设第\(k\)位有\(x\)个\(0\).那么第\(k\)位就有\(l-x\)个\(1\)
-
现在我们要看看这一堆\(0\)和\(1\)对原式有什么贡献
-
根据前置芝士，只有一个\(0\)和一个\(1\)才能有一个\(1\)
-
所以第\(1\)个\(0\)可以和其他\(l-x\)个\(1\)一一异或成为\(l-x\)个\(1\)
-
同理，第\(2\)个，第\(3\)个……都可以产生\(l-x\)个\(1\)
-
所以共可以产生\(x\cdot (l-x)\)个\(1\),而第\(k\)个\(1\)贡献的值为\(2^{k-1}\),所以总共贡献的值为
-
\(2^{k-1}\cdot x \cdot (l-x)\)
-
所以,如果我们设\(p\)为\(n\)的二进制位数的话
-
要使那个式子最大，首先要使\(2^{i-1}\cdot x \cdot (l-x)\)这个最大
-
我们发现\(2^{i-1}\)是常数，不看他，也就是要\(x\cdot (l-x)\)最大
-
假如你学过二次函数
-
该二次函数开口向下，有最大值
-
也就是当\(x=-\frac{b}{2a}=\frac{-l}{-2}=\frac{l}{2}\)时取最大值
-
这里要纠正一下，因为只有可能是整数，所以我们这里向下取整一下（和向上取整没区别）
-
原式就等于\(\left \lfloor \frac{l}{2}\right \rfloor\cdot (l-\left \lfloor \frac{l}{2}\right \rfloor)\)
-
于是我们就可以得到一个式子（注意，\(\sum\)具有结合律）
- 对于\(\sum_{i=1}^p2^{i-1}\)我们可以用等比数列的求和公式，它就变成了\(2^p-1\)
- 所以我们要求的就是
- 最后一个问题：\(p\)是什么？
- 我们立刻就会想到与\(\log n\)有关系，我们来手摸一下
- 如果是\(8=1000_{(2)}\)，\(\log 8=3\)，位数是\(4\),所以我们要加一
- 再来一个\(7=111_{2}\),\(\log 7 = 2....\),位数是\(3\),所以我们要向下取整在加一
- 归纳一下
- 于是代码就出来了
\(\mathcal{Code}\)
#include<bits/stdc++.h>
using namespace std;
#define int unsigned long long
const int MAXN = 5e5 + 7, mod = 1e9 + 7;
int T, n, l;
signed main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> T;
while (T--) {
cin >> n >> l;
if (n == 1) cout << 0 << endl;
else cout << ((l / 2 * (l - l / 2)) % mod * ((int)pow(2, (int)log2(n) + 1) - 1)) % mod << endl;
}
return kkksc03;
}
完结撒花✿✿ヽ(°▽°)ノ✿
标签：lfloor,right,frac,cdot,题解,sum,异或,EZEC,P6599 From： https://www.cnblogs.com/Phrvth/p/17045157.html