题意

给出一个$n$个数构成的序列,$a[1],a[2],a[3]…a[n]$。

给出$m$个需求，对于第$1\le i\le m$个需求$p_i,q_i$，表示如果在序列$a$中,如果存在$a[j],1\le j\le n$在二进制表示下的第$p_i$位为$1$，则需要在集合$S$中添加元素$q_i$。

给定一个$k$，求出从$0-2^k-1$中，除了序列$a$中的数最多可以选多少个数放入序列$a$保证集合$S$内的元素不变。

分析

考虑转化为补集：合法方案 = 总方案 - 不合法方案

考虑如何计算出不合法的方案。

令$f[i]$为二进制构成不超过$i$位的数中，不满足要求的数的个数。

考虑如何划分状态以便转移。

以第$i$是$0$还是$1$分类讨论：

如果第$i$位是$0$，其方案数显然为$f[i-1]$

考虑第$i$位是$1$的情况：

如果第$i$位为$1$要选的元素已经在集合内，那么方案数为$f[i-1]$

如果第$i$位为$1$要选的元素不在集合内，则方案数为$2^i$。

因此可以得到状态转移方程

$$ f[i]=f[i-1]+(f[i-1]/2^i) $$

此步的复杂度为$O(c)$（$c$为$q$的种数）

最后的方案数即$2^k-f[k-1]-n$。

预处理出集合$S$之后跑一遍$DP$即可$AC$本题

代码:

#include <iostream>
#include <vector>
#include <cstring>
#include <cstdio>

namespace wxy{
        __int128 f[65];
        unsigned long long b[1000005];
        bool vis[100000005];
        bool vs[65];
        std::vector<int> a[65];
        int n,m,c,k;
        typedef std::pair<int,int> PII;
        PII q[1000005];
        void print(__int128 x){
            if(x<0)putchar('-'),x=-x;
            if(x>9)print(x/10);
            putchar(x%10+'0');
        }
        __int128 ppp;
        void init(){
            ppp = 1;
            for (int i = 1; i <= 64; i++) ppp *= 2;
        }
        void main(){
            memset(vis,false,sizeof vis);
            memset(vis,false,sizeof vs);
            memset(f,0,sizeof f);
            std::cin >> n >> m >> c >> k;
            init();
            for (int i = 1; i <= n; i++) scanf("%lu",&b[i]);
            for (int i = 1; i <= m; i++){
                    std::cin >> q[i].first >> q[i].second;
                    a[q[i].first].push_back(q[i].second);
            }
            for (int i = 1; i <= n; i++){
                for (int j = k; j >= 0; j--)
                    if (b[i] >> j & 1) vs[j] = true;
            }
            bool pop[1000005];
            for (int i = 1; i <= m; i++){
                if (vs[q[i].first] && !pop[q[i].first]){
                    for (int j = 0; j < a[q[i].first].size(); j++) vis[a[q[i].first][j]] = true;
                }
                pop[q[i].first] = true;
            }
            for (int i = 0; i <= k; i++){
                if (i != 0) f[i] = f[i - 1];
                bool ck = false;
                for (int j = 0; j < a[i].size(); j++){
                    if (!vis[a[i][j]]){
                        __int128 www;
                        if (i < 64)www = 1ull * 1 << i;
                        else www = ppp;
                        f[i] = f[i] + www;
                        ck = true;
                        break; 
                    }
                } 
                if (!ck && i != 0) f[i] = f[i] + f[i - 1];
            }   
            __int128 a;
            if (k < 64) a = 1ull * 1 << k;
            else a = ppp;
            __int128 pppp = n;
            print(a - f[k - 1] - pppp);
        }
}signed main(){wxy::main();return 0;}