[ICPC2020济南L] Bit Sequence - 数位dp

[ICPC2020济南L] Bit Sequence - 数位dp

Description

定义 \(f(x)\) 表示 \(x\) 二进制表示的 \(1\) 的数量。给你n个是0或者1的数，再给你一个 \(L\)，问在区间 \([0,L]\) 之间有多少个数 \(x\) 满足 \(?i∈[0,m?1]，f(x+i) \bmod 2=a_i\)

Solution

核心观察是，\(x+i\) 只会频繁影响 \(a[0..6]\)，对于 \(a[7..]\) 的部分，最多只会发生一次进位

这次进位的影响，只和第 \(7\) 位往上连着的 \(1\) 的个数有关

数位 dp，设 \(f[pos][lim][sum][cnt]\) 表示从高到低处理到了第 pos 位（低位为 0）此时是否顶格，前面数位的和的奇偶性为 \(sum\)，从第 \(pos+1\) 位往高走的连续 \(1\) 的个数的奇偶性为 \(cnt\)

如果处理到了 \(pos<7\) 的状态，就转入一个暴力

#include 
using namespace std;

#define int long long

int a[105], b[105], siz, f[105][2][2][2], m, l;

int par(int x)
{
    return __builtin_parity(x);
}

int calc(int lim, int sum, int cnt)
{
    int ans = 0;
    int up = lim ? l % 128 : 127;
    for (int i = 0; i <= up; i++)
    {
        int flag = 1;
        for (int j = 0; j < m && flag; j++)
            if ((i + j < 128 && (par(i + j) ^ sum ^ a[j])) || (i + j >= 128 && (par(i + j) ^ sum ^ cnt ^ a[j])))
                flag = 0;
        ans += flag;
    }
    return ans;
}

int dfs(int pos, int lim, int sum, int cnt)
{
    int &ans = f[pos][lim][sum][cnt];
    if (~ans)
        return ans;
    ans = 0;
    if (pos < 7)
        ans = calc(lim, sum, cnt);
    else
        for (int i = 0; i <= (lim ? b[pos] : 1); i++)
            ans += dfs(pos - 1, lim && b[pos] == i, sum ^ i, i && (!cnt));
    return ans;
}

void generate_b()
{
    siz = 0;
    int t = l;
    while (t)
    {
        b[siz++] = t & 1;
        t /= 2;
    }
}

void solve()
{
    memset(f, -1, sizeof f);
    memset(a, 0, sizeof a);
    memset(b, 0, sizeof b);
    cin >> m >> l;
    for (int i = 0; i < m; i++)
        cin >> a[i];
    generate_b();
    cout << dfs(siz - 1, 1, 0, 0) << endl;
}

signed main()
{
    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }
}