NK52189L

数位dp稍微有难度的题

NK52189L Bit Sequence

题目大意

令f(x)= __builtin_parity(x)求在$[0,L]$的范围中满足$f(x),f(x+1),…,f(x+n-1)$与给定数组a相同的x的个数

分析

一开始很容易想到这个序列的性质去，然后发现n只有100，那么$x+n$如果不在第7位二进制位产生高位进位则不会对更高位产生影响，直接暴力计算即可，如果产生进位的话，那在第7位前面连续的1的个数也会对答案产生影响，按照这个进行数位dp即可。

代码

//
// Created by mrx on 2023/2/27.
//
#include <functional>
#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
#include <cmath>
#include <queue>
#include <array>
#include <map>

using i64 = long long;
std::array<int, 277> f;

void solve() {
    int m;
    i64 L;
    std::cin >> m >> L;
    std::vector<int> a(m);
    for (int i = 0; i < m; ++i)std::cin >> a[i];
    std::vector<int> bits;
    i64 x = L;
    do {
        bits.push_back(x & 1);
        x >>= 1;
    } while (x);
    std::vector dp(bits.size(), std::vector<i64>(8, -1));//pos,status

    auto cacal = [&](int status) -> i64 {
        int lmt = status & 1;
        int cnt1 = (status >> 2) & 1;
        int cnt2 = (status >> 1) & 1;
        i64 hi = lmt ? L % 128 : 127;
        i64 res = 0;
        for (int i = 0; i <= hi; ++i) {
            int ok = 1;
            for (int j = 0; j < m && ok; ++j) {
                if (i + j < 128) ok &= (f[i + j] ^ cnt1) == a[j];
                else ok &= (f[i + j] ^ cnt1 ^ cnt2) == a[j];
            }
            res += ok;
        }
        return res;
    };
    std::function<i64(int, int)> dfs = [&](int pos, int status) -> i64 {
        auto& res = dp[pos][status];
        if (res != -1)return res;
        else if (pos <= 6)return res = cacal(status);
        res = 0;
        int cnt1 = (status >> 2) & 1, cnt2 = (status >> 1) & 1, lmt = status & 1;
        int up = lmt ? bits[pos] : 1;
        for (int i = 0; i <= up; ++i) {
            int nxl = lmt & (i == up), nxc1 = cnt1 ^ i, nxc2 = (!cnt2) & i;
            res += dfs(pos - 1, (nxl) | (nxc1 << 2) | (nxc2 << 1));
        }
        return res;
    };
    std::cout << dfs((int(bits.size())) - 1, 1) << '\n';
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    int t;
    std::cin >> t;
    for (int i = 0; i < 277; ++i)f[i] = __builtin_parity(i);
    while (t--) {
        solve();
    }
    return 0;
}