我居然还记得矩乘怎么写 真是感人

懵逼的 题目

BZOJ

扯淡的 题解

{x xor 3x = 2x} => {x xor 2x = 3x} => {x xor 2x = x + 2x} => {x没有相邻的1}

没有相邻的$1$, 第一问用数位DP就完事了

第二问我没有想到会有两个$1$中间隔着不只一个$0$的情况然后写了个$2^\frac{n}{2} \cdot 2^{n - \frac{n}{2}} - 1$就GG了

我们发现第二问这个玩意是可以递推的, 设答案为$S_n$, 如果在$S_{n - 1}$后面加$0$(指二进制下), 或者在$S_{n - 2}$后面加$01$就包含了所有的情况, 所以$S_n = S_{n - 1} + S_{n - 2} \to \{S_n\} = \{fib_n\}$, 矩乘一下就完事了

沙茶的 代码

/**************************************************************
    Problem: 3329
    User: Cansult
    Language: C++
    Result: Accepted
    Time:48 ms
    Memory:1296 kb
****************************************************************/

#include <iostream>
#include <cstdio>
#include <cstring>
#define LL long long
#define MOD (1000000000 + 7)
#define MAXL (60 + 5)
using namespace std;
struct matrix {
    LL n, m, zh[3][3];
}sou, m1;
LL n, a[MAXL], f[MAXL][2][2]; // 当前在第i位, 是否卡上界, 末尾是否为1的符合条件的x的个数
void solve() {
    memset(f, 0, sizeof(f));
    f[0][1][0] = 1;
    for (int i = 0; i < a[0]; i++)
        for (int up = 0; up <= 1; up++)
            for (int ln = 0; ln <= 1; ln++)
                for (int nn = 0; nn <= 1; nn++) {
                    if (up && nn > a[i + 1]) continue;
                    if (ln && nn)   continue;
                    int nup = (up & (a[i + 1] == nn));
                    f[i + 1][nup][nn] += f[i][up][ln];
                }
    LL ans = 0;
    for (int up = 0; up <= 1; up++)
        for (int ln = 0; ln <= 1; ln++)
            ans += f[a[0]][up][ln];
    printf("%lld\n", ans - 1);
}
matrix mult(matrix a, matrix b) {
    matrix re;
    re.n = a.n, re.m = b.m;
    memset(re.zh, 0, sizeof(re.zh));
    for (int i = 1; i <= a.n; i++)
        for (int j = 1; j <= b.m; j++)
            for (int k = 1; k <= b.n; k++)
                re.zh[i][j] = (re.zh[i][j] + (a.zh[i][k] * b.zh[k][j]) % MOD) % MOD;
    return re;
}
matrix ksm(LL b) {
    if (b == 1) return m1;
    matrix re = ksm(b >> 1);
    re = mult(re, re);
    if (b & 1)  re = mult(re, m1);
    return re;
}
int main() {
    sou.n = 1, sou.m = 2, sou.zh[1][1] = sou.zh[1][2] = 1;
    m1.n = m1.m = 2, m1.zh[1][2] = m1.zh[2][1] = m1.zh[2][2] = 1;
    int t;
    scanf("%d", &t);
    while (t--) {
        scanf("%lld", &n);
        a[0] = 0;
        while (n >= (1ll << a[0])) ++a[0];
        for (int i = 1; i <= a[0]; i++)  a[i] = ((n & (1ll << (a[0] - i))) > 0);
        solve();
        printf("%lld\n", mult(sou, ksm(n)).zh[1][2]);
    }
    return 0;
}

By 准备退役旅游的Cansult