F题题解：

大致思路：

先看操作成功的规律：

对于一个 $a[i]$ 和 $m$ ，按二进制来看 $a_i \operatorname{and} m$ 的 $1$ 最低位（即 lowbit）加进 $a[i]$ 中，会变为 $0$ ，并进位，而更低位的值不会变化。下一次 $a_i \operatorname{and} m$ 的 $1$ 最低位将会变高，而当 $a[i]$ 的 $1$ 最低位比 $m$ 的 $1$ 最高位还高时， $a[i]$ 的值将不会发生变化。

举个例子：如果 $a[i] = 101110,m = 110111$ （二进制表示）

第一次操作：

$\color{black}{a[i] \operatorname{and} m = 1001} \color{red}{1} \color{black}{0}$

$\color{black}{a[i] (a[i] \operatorname{and} m) = 10101} \color{red}{0} \color{black}{0}$
第二次操作：

$\color{black}{a[i] \operatorname{and} m = 10} \color{red}{1} \color{black}{00}$

$\color{black}{a[i] (a[i] \operatorname{and} m) = 1101} \color{red}{0} \color{black}{00}$
第三次操作：

$\color{black}{a[i] \operatorname{and} m =} \color{red}{1} \color{black}{00000}$

$\color{black}{a[i] (a[i] \operatorname{and} m) = 100} \color{red}{0} \color{black}{1000}$

之后 $a[i] \operatorname{and} m=0$ ， $a[i]$ 的值将不再变化。

$m$ 二进制最高 $30$ 位，故 $a[i]$ 最多变化 $30$ 次。

我们只需求出小于等于 $30$ 次变化的概率；

然后用 $1$ 减掉前面的概率，算出大于等于 $31$ 次变化的概率（对应的 $a[i]$ 都相等）。

用概率乘上对应的 $a[i]$ 即可算出总期望。

变化 $i$ 次的概率为： $\frac{C^i_k}{2^k}$

使用快速幂计算逆元与 $2$ 的幂次。

时间复杂度 $\theta(32n)$ 。

最终代码：

#include<bits/stdc++.h>
#define ll long long
#define MO 1000000007ll
#define MXN 1000002
using namespace std;
inline void rd(ll &x){x=0;short f=1;char c=getchar();while((c<'0'||c>'9')&&c!='-') c=getchar();if(c=='-') f=-1,c=getchar();while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();x*=f;}

ll T=1,n,m,k,a[MXN],ans;
ll p[32];
ll ksm(ll a,ll b){
    ll s=1;
    while(b){
        if(b&1) s*=a,s%=MO;
        a*=a,a%=MO;
        b>>=1;
    }
    return s;
}
ll cal(ll n,ll m){//求组合数
    ll ans=1;
    for(ll i=1,j=n-m+1;i<=m;i++,j++)
        ans*=j*ksm(i,MO-2)%MO,ans%=MO;
    return ans;
}
void solve(){
    rd(n),rd(m),rd(k);
    for(ll i=0;i<=30;i++)
        p[i]=cal(k,i)*ksm(ksm(2,k),MO-2)%MO,
        p[31]+=MO-p[i];
    p[31]=(1+p[31])%MO;
    for(ll i=1,x;i<=n;i++){
        rd(x);
        for(ll j=0;j<=31;j++){
            ans+=x*p[j]%MO,ans%=MO;
            x+=x&m;
        }
    }
    pt(ans);
}int main(){while(T--) solve();}

题解 | #变化的数组#

F题题解：

大致思路：

最终代码：