[BZOJ 3329]Xorequ

Description

题库链接

给出 \(n\) ，分别求 \(\leq n\) 和 \(\leq 2^n\) 的满足方程 \[x\oplus 3x=2x\] 的正整数解个数。

\(1\leq n\leq 10^{18}\)

Solution

显然满足 \(x\oplus 2x=3x\) 即要满足 \(x\&(x<<1)=0\) 。其含义就是数的二进制相邻的两位不能同为 \(1\) 。

考虑第一种情况，即 \(\leq n\) 。容易发现其实可以数位 \(DP\) 。 \(f_{i,1/0}\) 为 \(i\) 位二进制的最高位为 \(1/0\) 的满足条件的非负整数的个数。

\[\begin{aligned}f_{i,0}&=f_{i-1,1}+f_{i-1,0}\\f_{i,1}&=f_{i-1,0}\end{aligned}\]

然后按位计算即可。

对于 \(\leq 2^n\) 的情况，容易发现其对具体的某一位是没有约束的，直接用矩阵加速上述转移方程即可。

Code

#include <bits/stdc++.h>

using namespace std;

const int yzh = 1e9+7;

long long f[100][2], n;

int t;

struct mat {

    int a[2][2];

    mat () {a[0][0] = a[0][1] = a[1][0] = a[1][1] = 0; }

    mat operator * (const mat &b) const {

    mat ans;

    for (int i = 0; i < 2; i++)

        for (int j = 0; j < 2; j++)

        for (int k = 0; k < 2; k++)

            (ans.a[i][j] += 1ll*a[i][k]*b.a[k][j]%yzh) %= yzh;

    return ans;

    }

}S, T;

mat quick_pow(mat S, mat T, long long t) {

    while (t) {

    if (t&1) S = S*T;

    t >>= 1, T = T*T;

    }

    return S;

}

void pre() {

    f[0][0] = f[0][1] = 1;

    for (int i = 1; i <= 90; i++)

    f[i][0] = f[i-1][0]+f[i-1][1], f[i][1] = f[i-1][0];

}

long long get_ans1(long long x) {

    int a[100], tot = -1; long long ans = 0;

    while (x) a[++tot] = x%2, x /= 2; a[tot+1] = 0;

    for (int i = tot; i >= 0; i--) {

    if (a[i] == 1) ans += f[i][0];

    if (a[i] == 1 && a[i+1] == 1) break;

    if (i == 0) ++ans;

    }

    return ans-1;

}

int get_ans2(long long x) {

    S.a[0][0] = S.a[0][1] = 1;

    T.a[0][0] = T.a[1][0] = T.a[0][1] = 1; T.a[1][1] = 0;

    S = quick_pow(S, T, x-1);

    return S.a[0][0]+S.a[0][1];

}

void work() {

    pre(); scanf("%d", &t);

    while (t--) {

    scanf("%lld", &n);

    printf("%lld\n%d\n", get_ans1(n), get_ans2(n)%yzh);

    }

}

int main() {work(); return 0; }

巴特西

[BZOJ 3329]Xorequ

Description

Solution

Code

最新文章

热门文章