题解 | # B. Modulo Sum #

$[bitset优化(01背包)]$

题目一：https://codeforces.com/problemset/problem/577/B

普通的 $01$ 背包时间复杂度为 $O(nm)$ 超时，可用 $bitset$ 优化至 $O(\frac{nm}{64})$

$bitset$ 存储 $m$ 的余数是否可达

这部分代码的意思是直接异或以及异或它的余数

bitset<20050> now_bit = bit;
now_bit <<= a[i];
bit |= now_bit;
bit |= (now_bit >> m);

总代码：

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

#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;


void solve(){
    
    int n, m; cin >> n >> m;
    vector<int> a(n + 10);
    for(int i = 1; i <= n; i ++){
        cin >> a[i];
        a[i] %= m;
        if(a[i] == 0){
            cout << "YES" << endl;
            return ;
        }
    }
    bitset<20050> bit;
    bit.set(0);
    
    for(int i = 1; i <= n; i ++){
        bitset<20050> now_bit = bit;
        now_bit <<= a[i];
        bit |= now_bit;
        bit |= (now_bit >> m);
        if(bit.test(m)){
            cout << "YES" << endl;
            return ;
        }
    }
    cout << "NO" << endl;
    return ;
}

signed main(){
    HelloWorld;

    int tt = 1; 
    while(tt --) solve();
    return 0;
}

题目二：https://ac.nowcoder.com/acm/problem/276144

仍然可以用 $bitset$ 解决，建立 $bitset$ 的 $dp$ 数组来模拟每一层可以到达的值

vector<bitset<250010> > dp(n + 10);
dp[0].set(0);
for(int i = 1; i <= n; i ++){
    for(int j = 1; j <= m; j ++){
        dp[i] |= (dp[i - 1] << adj[i][j]);
    }
}

总代码：

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

#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;


void solve(){
    int n, m; cin >> n >> m;
    vector<vector<int> > a(n + 1, vector<int> (m + 1));
    for(int i = 1; i <= n; i ++){
        for(int j = 1; j <= m; j ++) cin >> a[i][j];
    }
    vector<bitset<250100> > dp(n + 10);
    dp[0].set(0);
    for(int i = 1; i <= n; i ++){
        for(int j = 1; j <= m; j ++){
            dp[i] |= (dp[i - 1] << a[i][j]);
        }
    } 
    int k; cin >> k;
    int ans = 1e18;
    for(int i = 250000; i >= 0; i --){
        if(dp[n].test(i)) ans = min(ans, abs(k - i));
    }
    cout << ans << endl;
    return ;
}

signed main(){
    HelloWorld;

    int tt = 1; 
    while(tt --) solve();
    return 0;
}

题目三：https://ac.nowcoder.com/acm/contest/132/C?&headNav=www

和上一题有些类似，不多说

总代码：

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

#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;


void solve(){
    
    int n; cin >> n;
    vector<int> l(n + 1), r(n + 1);
    for(int i = 1; i <= n; i ++) cin >> l[i] >> r[i];
    vector<bitset<1000100> > dp(n + 10);
    dp[0].set(0);
    for(int i = 1; i <= n; i ++){
        for(int j = l[i]; j <= r[i]; j ++){
            dp[i] |= (dp[i - 1] << (j * j));
        }
    }
    cout << dp[n].count() << endl;
    return ;
}

signed main(){
    HelloWorld;

    int tt = 1; 
    while(tt --) solve();
    return 0;
}