【算法题解】AND-array • Martian148

Question#

对于一个长度为 $n$ 的序列 $a$ ，我们定义其 AND 数组 $f(a)$ 如下：

f(a)_k = \sum\limits_{1 \le i_1 \lt i_2 \lt \ldots \lt i_k \le n} a_{i_1} \& a_{i_2} \& \ldots \& a_{i_k}

换句话说， $f(a)_k$ 是对序列 $a$ 中所有长度为 $k$ 的子序列的元素按位与的和。

序列 $a$ 对你而言是未知的。但你被提供了一个长度为 $n$ 的序列 $b$ ，满足对所有 $1 \le i \le n$ ，都有 $b_i \equiv f(a)_i \pmod{10^9 + 7}$ 。你的任务是基于给定的序列 $b$ 还原序列 $a$ 。

1\le n\le 10^5, 0\le b_i\le 10^9+7,0\le a_i<2^{29}

Solution#

我们设二进制的第 $p$ 位在数组 $a$ 中出现了 $c_p$ 次，那么对于一个长度为 $k$ 的子序列，它的 AND 在第 $p$ 位为 $1$ 的选法有

\binom{c_p}{k}

种，所以第 $p$ 位对 $f(a)_k$ 的贡献就是

2^{p} \cdot\binom{c_{p}}{k}

于是

b_{k} \equiv f(a)_{k} \equiv \sum_{p=0}^{28} 2^{p}\binom{c_{p}}{k} \quad\left(\bmod 10^{9}+7\right)

这就是整题的本质。

现在我们要把每个 $c_p$ 求出来

倒着枚举 $k = n, n-1, \ldots, 1$ 。

因为：

如果 $c_p < k$ ，那么 $\binom{c_p}{k} = 0$
如果 $c_p = k$ ，那么 $\binom{c_p}{k} = 1$
如果 $c_p > k$ ，那么它的贡献可以用之前已经知道的 $c_p$ 算出来

所以对当前 $k$ ，先把所有 $c_p > k$ 的贡献减掉：

x_k = b_k - \sum_{c_p > k} 2^p \binom{c_p}{k} \quad (\bmod\ MOD)

那么剩下的就是：

x_k = \sum_{c_p = k} 2^p

于是我们看 $x_k$ 的哪一位为 $1$ 就代表这一位对应的 $c_p=k$

现在我们得到了 $c_p$ 要构造数组，暴力能放就放就好了

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1e9 + 7;
const int MAXN = 1e5 + 5;
ll Fac[MAXN], InvFac[MAXN];

ll pow(ll a, ll b) {
    ll res = 1;
    while (b) {
        if (b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

void init() {
    Fac[0] = 1;
    for (int i = 1; i < MAXN; i++) Fac[i] = Fac[i - 1] * i % MOD;
    InvFac[MAXN - 1] = pow(Fac[MAXN - 1], MOD - 2);
    for (int i = MAXN - 2; i >= 0; i--) InvFac[i] = InvFac[i + 1] * (i + 1) % MOD;
}

ll C(int n, int m) {
    if (m > n || m < 0) return 0;
    return Fac[n] * InvFac[m] % MOD * InvFac[n - m] % MOD;
}

void solve() {
    int n; cin >> n;
    vector<ll> b(n + 1);
    vector<ll> cnt(29, 0);
    for (int i = 1; i <= n; i++) cin >> b[i];
    for (int k = n; k >= 1; k--) {
        ll val = b[k];
        for (int j = 0; j < 29; j++) {
            val -= (1LL << j) * C(cnt[j], k) % MOD;
            val = (val % MOD + MOD) % MOD;
        }

        for (int j = 0; j < 29; j++) 
            if (val >> j & 1) {
                cnt[j] = k;
            }
    }

    vector<ll> a(n + 1);
    for (int i = n; i >= 1; i--) {
        for (int j = 0; j < 29; j++) {
            if (cnt[j] > 0) a[i] += 1LL << j, cnt[j]--;
        }
    }
    

    for (int i = 1; i <= n; i++) cout << a[i] << " \n"[i == n];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    init();
    int t; cin >> t;
    while (t--) solve();
    return 0;
}

cpp