CF 1670F Jee, You See?

题目描述

https://codeforces.com/contest/1670/problem/F

简要题意：给定 $n,l,r,z$，求有多少个长度为 $n$ 的序列 $a_i$，满足 $l\le\sum_{i=1}^na_i\le r$ 且 $\bigoplus_{i=1}^na_i=z$，其中 $\oplus$ 为异或

$n\le 1000,1\le l,r \le 10^{18},z\le 10^{18}$

Solution

考虑数位 $dp$，我们令 $f[o][i]$ 表示填到了第 $o$ 位，第 $o$ 位最多能选 $i$ 个 $1$，注意到 $f[o][i]$ 向 $f[o-1][k]$ 转移时，能选的 $1$ 的个数为 $i\times 2$ 加上第 $o-1$ 位是否为 $1$，注意到我们一次最多只能选 $n$ 个 $1$，所以我们第二维对 $n$ 取 $min$ 即可

时间复杂度 $O(64n^2)$，注意并不需要使用记忆化搜索

#include <iostream>
#define maxn 1010
#define ll long long
using namespace std;

const int p = 1000000007;
inline int add(int x, int y) { return (x += y) >= p ? x - p : x; } 

int C[maxn][maxn];
void init_C(int n) {
    for (int i = 0; i <= n; ++i) C[i][0] = 1;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= i; ++j) C[i][j] = add(C[i - 1][j], C[i - 1][j - 1]);
}

const int N = 60;

int n;
ll l, r, z;

int f[64][maxn];
int calc(ll d) {
    fill(f[0], f[0] + 64 * maxn, 0); 
    f[60][0] = 1;
    for (int o = 60; o; --o)
        for (int i = 0; i <= n; ++i) {
            int ones = 2 * i + (d >> o - 1 & 1);
            for (int j = z >> o - 1 & 1; j <= min(n, ones); j += 2)
                f[o - 1][min(n, ones - j)] = add(f[o - 1][min(n, ones - j)], 1ll * C[n][j] * f[o][i] % p);
        }
    int res = 0;
    for (int i = 0; i <= n; ++i) res = add(res, f[0][i]);
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> l >> r >> z; init_C(n);
    cout << add(calc(r), p - calc(l - 1)) << "\n";
    return 0;
}