题解 | 变化的数组

#include<bits> using namespace std; typedef long long LL; const int N = 1e5 + 10, mod = 1e9 + 7; LL n, m, k; // 快速幂 就是 x^4 = x^2*x^2 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; } // C(上m,下n) = A(m,n) / A(m,m) // A(m,n) =n*(n-1)*...(n-m+1) LL C(LL n, LL m) { LL res = 1; for(LL i=1,j=n; i<=m; i++,j--) { res = res * j % mod; // 为了能够mod 使用了乘法逆元 // 也就是 res / i = res * ksm(i,mod-2)%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; // a的期望是不同的操作次数下 a最后的值 for(j=0; j<=k && (a&m); j++) { LL c = C(k, j); // 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; } // 如果 a&m==0，则不论操作还是不操作都一样了，因为是 a+a&m = a // 所以提前退出，但需要看现在还剩多少排列组合要继续算期望 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; }</bits>