题解 | 变化的数组

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 1e5 + 10, mod = 1e9 + 7;

LL n, m, k;

LL ksm(LL x, LL y) {
    LL res = 1;
    while( y ) {
        if(y & 1) res = res * x % mod;
        x = x * x % mod;
        y >>= 1;
    }
    return res;
}

LL C(LL n, LL m) {
    LL res = 1;
    for(LL i=1,j=n; i<=m; i++,j--) {
        res = res * j % mod;
        res = res * ksm(i, mod - 2) % mod;
    }
    return res;
}

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

    cin >> n >> m >> k;
    LL res = 0;
    for(int i=1; i<=n; i++) {
        LL a; cin >> a;
        LL t = 0;
        int j;
        for(j=0; j<=k && (a&m); j++) {
            LL c = C(k, j);
            res += c * a;
            res %= mod;
            a += a & m;
            // a %= mod;
            t += c;
            t %= mod;
            // res += c[k][j] * get(a, j);
            // res %= mod;
        }
        if(j <= k) {
            res += a * ((ksm(2, k) - t + mod) % mod);
            res %= mod;
        }
    }
    LL inv = ksm(ksm(2, k), mod - 2);
    res *= inv;
    res %= mod;
    cout << res;

    return 0;
}

观察发现一定少量操作之后&运算的结果是零；对数操作的结果不要取模（显然）