题解 - [Luogu P5177] 签到

发表于 更新于 分类于 ， 本文字数： 467 阅读时长 ≈ 2 分钟

强烈谴责这种起无意义标题的做法

题目链接

原始题面

题目描述

求 \(\sum_{i=1}^n \sum_{j=1}^n i \ xor \ j \in [\min(i,j),\max(i,j)]\)

由于答案可能过大，输出答案对 \(10^9+7\) 取模的值

输入输出格式

输入格式

第一行，一个整数 \(T\), 为数据组数。下面 \(T\) 行，每行一个整数 \(n\)

输出格式

对于每行数据，输出答案

输入输出样例

输入样例 #1

1
2
3
4
3
10
100
1000

输出样例 #1

1
2
3
20
2634
325502

说明

第一组样例解释：符合题意的 \((i,j)\) 有 \(20\) 对

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
i=1 j=3 i^j=2
i=1 j=5 i^j=4
i=1 j=7 i^j=6
i=1 j=9 i^j=8
i=2 j=6 i^j=4
i=2 j=7 i^j=5
i=2 j=10 i^j=8
i=3 j=1 i^j=2
i=3 j=6 i^j=5
i=3 j=7 i^j=4
i=3 j=10 i^j=9
i=5 j=1 i^j=4
i=6 j=2 i^j=4
i=6 j=3 i^j=5
i=7 j=1 i^j=6
i=7 j=2 i^j=5
i=7 j=3 i^j=4
i=9 j=1 i^j=8
i=10 j=2 i^j=8
i=10 j=3 i^j=9

对于 27% 的数据，\(T\le 5, n \le 1000\)

对于 54% 的数据，\(T\le 20, n \le 5 \times 10^5\)

对于 90% 的数据，\(T\le 10^5, n \le 10^{18}\)

最后一个点，\(T=3\times 10^6 \ ,\ n\le 10^{18}\)

解题思路

首先规范一些记号，题目要求的是

\[ \sum_{i=1}^n\sum_{j=1}^n[\min\{i,j\}\leqslant (i\oplus j)\leqslant \max\{i,j\}] \]

显然，上式等价于

\[ 2\sum_{i=1}^n\sum_{j=1}^{i-1}[j\leqslant (i\oplus j)\leqslant i] \]

固定 \(i\), 则 \(j\) 能产生贡献当且仅当 \(j\) 二进制最高位为 \(i\) 二进制次高位

代码参考

Show code

Luogu_P5177view raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/*
 * @Author: Tifa
 * @Description: From <https://github.com/Tiphereth-A/CP-archives>
 * !!! ATTENEION: All the context below is licensed under a 
 *  GNU Affero General Public License, Version 3.
 *  See <https://www.gnu.org/licenses/agpl-3.0.txt>.
 */
#include <bits/stdc++.h>
const u64 mod = 1e9 + 7;
u64 f(u64 n) {
  n %= mod;
  return (n + 1) * n / 2 % mod;
}
u64 a[64];
int main() {
  for (int i = 1; i < 64; ++i) a[i] = (f((1ull << i - 1) - 1) + a[i - 1]) % mod;
  int t;
  scanf("%d", &t);
  while (t--) {
    u64 n;
    scanf("%llu", &n);
    printf(
      "%llu\n",
      (a[63 - __builtin_clzll(n)] + f(n - (1ull << 63 - __builtin_clzll(n)))) *
        2 % mod);
  }
}