位运算好题

Posted on Edited on In Word count in article: 564 Reading time ≈ 2 mins.
还是挺重要一东西

位运算是一个十分有助的工具

还是要好好学的

P6034 Ryoku 与最初之人笔记

题目大意

求： \[ \sum_{a=0}^n\sum_{b=a+1}^n[a\equiv b\pmod{a\wedge b}] \] 当然，最开始的开始，是通过暴力运算直接拿的\(20pt\)的好成绩

分析

遇到位运算，换元是不错的处理方法

令：\(y=a \& b,\;a=x+y,\;b=y+z\)，那么有：\(a|b=x+y+z,a \wedge b=x+z\)

那么通过这个换元，可以得到一些好东西： \[ (a\wedge b)|(b-a)=(x+z)|(z-x) \] 那么就发现了，当且仅当\(x=0\)时，这个才能成立

所以说原式可以写为： \[ \sum_{a=0}^n\sum_{b=a+1}^n[a\equiv b\pmod{\verb|a^b|}]=\sum_{a=1}^n\sum_{b=a+1}^n[\verb|a&b|==a] \] 那么定义 \[ f(x)=\sum_{i=1}^{x-1}[\verb|i&x|==i] \] 显然这个可以写成是： \[ f(x)=2^{cnt_x}-1 \] 其中\(cnt_x\)表示\(x\)再二进制下\(1\)的个数

所以原式交换求和顺序后可以变成下面的样子： \[ ans=\sum_{i=1}^n2^{f(i)}-n\\ 令：s(n)=\sum_{i=1}^ns^{f(i)} \] 然后，还有这样一个性质： \[ f(i<<1)=f(i)\\ f(i<<1|1)=f(i)+1 \] 所以求和的时候，可以分奇偶求： \[ \begin{aligned} s(2n)&=\sum_{i=1}^{2n}s^{f(i)}\\ &=\sum_{i=1}^n2^{f(2i-1)}+\sum_{i=1}^n2^{f(2i)}\\ &=\sum_{i=1}^n2^{f(i-1)+1}+\sum_{i=1}^n2^{f(i)}\\ &=2(1+\sum_{i=1}^{n-1}2^{f(i)})+\sum_{i=1}^{n-1}2^{f(i)}+2^{f(n)}\\ &=3\sum_{i=1}^{n-1}2^{f(i)}+2^{f(n)}+2\\ &=3s(n-1)+2^{f(n)}+2 \end{aligned} \] 然后乱搞就完了

Code

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <bits/stdc++.h>
#define lowbit(x) (x & -x)

using namespace std;

typedef long long ll;
const int maxn = 1e5 + 10;
const int mod = 1e9 + 7;

inline ll __read()
{
    ll x(0), t(1);
    char o (getchar());
    while (o < '0' || o > '9') {
        if (o == '-') t = -1;
        o = getchar();
    }
    for (; o >= '0' && o <= '9'; o = getchar()) {
        x = (x << 1) + (x << 3) + (o ^ 48);
    }
    return x * t;
}

inline int Pow(ll x, int y)
{
    int ans(1);
    while (y) {
        if (y & 1) ans = ans * x % mod;
        x = x * x % mod;
        y >>= 1;
    }
    return ans % mod;
}

inline int count(ll x)
{
    int cnt(0);
    while (x) {
        x -= lowbit(x);
        ++cnt;
    }
    return Pow(2, cnt);
}

inline ll Sum(ll x)
{
    if (x == 0) return 0;
    if (x & 1) return (Sum(x ^ 1) + count(x)) % mod;
    ll temp = Sum((x >> 1) - 1);
    return (temp * 3 + count(x >> 1) + 2) % mod;
}

signed main()
{
    ll n = __read();
    printf ("%lld\n", ((Sum(n) - n) % mod + mod) % mod);
    system("pause");
}