＃468. 函数求和

链接：函数求和

思路：硬求复杂度不行，这种题一般考虑某某数对答案的贡献，这题考虑 i 对答案的贡献。
一个数二进制位最多是k位，先考虑a [1]，想让 a[1] & x != a[1]，那么 a[1]的二进制位上如果是1，那么对应的x那一位上可以是0，a[1]共有cnt1个位是1，那就有 qpow(2, cnt1) - 1种填法，对于a[1]为0的位，x随便填什么都行。
该开始考虑a[2]了，想要在这一位产生贡献，那么首先一定有x & a[1] == a[1]，所以上一次搞完之后要有 x |= a[1]。
那么现在可以这样子想了：

a[i]  1   1                          0    0
x     1   0                          1    0
结论  定  不定（可变0或1，但是有限制）  定   不定（可变0或1，无限制）

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 200 + 5, mod = 998244353;
int a[N];
int qpow (int x, int n)
{
    
    int ret = 1;
    while (n) {
    
        if (n & 1) ret = ret * x % mod;
        x = x* x % mod;
        n >>= 1;
    }
    return ret;
}
signed main ()
{
    
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];
    int x = 0;
    int ans = 0;
    for (int i = 1; i <= n; i++) {
    
        if (a[i] == 0) continue;
        int cnt1 = 0, cnt2 = 0;
        for (int j = 0; j < k; j++){
    
            int p1 = (a[i] >> j) & 1, p2 = (x >> j) & 1;
            if (p1 && !p2) cnt1++;
            if (!p1 && !p2) cnt2++;
        }
        ans += (qpow(2, cnt1) - 1) * qpow(2, cnt2) % mod * i % mod;
        x |= a[i];
    }
    cout << (ans + mod) % mod;
    return 0;
}