#468. 函数求和

题目描述：

给n个整数a1,a2,…,an和正整数k满足$(0≤ai≤2^k−1)$。

定义函数f(x)为满足𝑎𝑖&𝑥≠𝑎𝑖的最小的i，当满足条件的i不存在时 f(x)=0。

求 $\sum_{i=0}^{2^k-1}{f(i)}$。 由于答案可能很大，输出答案取模998244353后的值

思路：

考虑每个i产生的贡献，即通过计算 $f(x) = i$的x的数量来计算答案

现在考虑什么情况下 a[i] & x != a[i]，我们从二进制的角度来考虑问题，只需要使的至少存在一位j，满足a[i]的第j位是1，x的第j位是0即可，其他位无所谓，但是如果计算的时候其他位都是无所谓的话就会重复计数，比如1101，计算第1位时，发现是1，那就是满足他的x的形式可以是ppp0，p表示0或1，数量就是 $2^3$，计算第三位时，发现是1，那满足他的x的形式是p0pp，算出来是 $2^3$，但是这样会导致重复计数，第1位是0的时候已经计算过了，所以应该把第一位当1看待，那其实答案是 $2^2$

所以我们思路就是：用一个num记录k位中还有几位没有被使用过，对于每个输入的数，我们拆成二进制来计算，如果当前位j是1，且第j位还没被用过，说明会对答案产生 $2^{num-1}*i$的贡献，然后更新掉第j位和num值

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, k;
ll x;
bool vis[100];

void work(){
    cin >> n >> k;
    ll ans = 0;
    ll num = k;
    for(ll i = 1; i <= n; ++i){
        cin >> x;
        for(ll j = 0; j < k; ++j){
            if((x & (1ll << j)) && !vis[j]){
                --num;
                ans += (((1ll << num) % mod) * i) % mod;
                ans %= mod;
                vis[j] = 1;
            }
        }
    }
    cout << ans << endl;
}


int main(){
    io;
    work();
    return 0;
}