题解：CF2252E Generational Triplets

· · 题解

易知题目条件的充要条件如下：

  1. 2 \times (a \operatorname{and} c) = a \oplus c
  2. 1 \le a < c \le n

证明需要用到下面的引理（其实是常识），是容易的，不再赘述。

:::info[引理]

\forall a, c \in \N, 2 \times (a \operatorname{and} c) + (a \oplus c) = a + c

证明：每位单独考虑，显然有：

a \operatorname{or} c &= (a \operatorname{and} c) + (a \oplus c) \\ a + c &= (a \operatorname{and} c) + (a \operatorname{or} c) \end{cases}

上式带入下式即证。

:::

对于条件 1，我们发现左侧的系数 2 就相当于左移。因此 a \oplus c 的第 w 位确定后，a \operatorname{and} c 的 w - 1 位也随之确定下来。并且 a \oplus c 的最低位必须是 0。

考虑数位 dp，我用 f(w, x, l_1, l_2, l, g) 表示当前考虑第 w 位，a \operatorname{and} c 的该位钦定为 x，l_1, l_2 分别表示 a, c 是否卡到上界 n（为了使 a, c \le n），l 表示 a 前面是否全是 0（为了使 a \ge 1），g 表示当前 c 是否卡着 a（为了使 a < c）。

转移等具体见代码：

:::info[code]

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 65;
const int MOD = 1e9 + 7;
int ttt, W;
ll n, f[N][2][2][2][2][2];

ll solve(int w, int x, bool l1, bool l2, bool l, bool g){
    ll &res = f[w][x][l1][l2][l][g];
    if(res != -1) return res;
    int u1 = l1 ? ((n >> w) & 1) : 1, u2 = l2 ? ((n >> w) & 1) : 1;
    if(!w){
        res = 0;
        for(int i = 0; i <= u1; i++){
            for(int j = 0; j <= u2; j++){
                if(g && j < i) continue;
                if(i || !l) res += ((i ^ j) == 0 && (i & j) == x);
            }
        }
        res %= MOD;
        return res;
    }
    res = 0;
    for(int i = 0; i <= u1; i++){
        for(int j = 0; j <= u2; j++){
            if(g && j < i) continue;
            if((i & j) != x) continue;
            res = (res + solve(w - 1, (i ^ j), l1 && i == u1, l2 && j == u2, l && i == 0, g && i == j)) % MOD;
        }
    }
    return res;
}

int main(){

    ios :: sync_with_stdio(false);
    cin >> ttt;
    while(ttt--){
        cin >> n;
        memset(f, -1, sizeof(f));
        W = __lg(n);
        cout << solve(W, 0, 1, 1, 1, 1) << '\n';
    }

    return 0;
}

:::