SOS dp

ACM

一类有关位运算的dp

教程链接

SOS dp解决的问题

给定一个数组A[], 求$ F(mask) = \sum A[i], mask \& i==i $
这类问题的时间复杂度为$ O(2^n·n) $
解决一类数字与为0的计数问题

special pairs

题解

要求统计A[i]&A[j]==0的对数
通过这一类dp的要求，我们统计有多少个

ac code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define ls (rt<<1)
#define rs (rt<<1|1)
#define mid (l+r>>1)
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define lowbit(x) (x&(-x))
#define inc(i, l, r) for(int i=l; i<=r; i++)
#define dec(i, r, l) for(int i=r; i>=l; i--)
const int inf = 0x3f3f3f3f;
const int maxn = 1e6+10;
const double pi = acos(-1.0);
const double eps = 1e-7;
const int mod = 1e9+7;
int readint()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
ll readll(){
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n, m;
const int N = 20;
ll dp[(1<<20)+10][22];
int tt[(1<<20)+10];
int num[(1<<20)+10];
int main()
{
    int _;
    _ = readint();
    while(_--){
        n=readint();
        inc(i, 1, n){
            num[i] = readint();
            tt[num[i]]++;
        }
        for(int mask =0; mask<(1<<N); mask++){
            dp[mask][0] = tt[mask];
            if(mask&1) dp[mask][0] += tt[mask^1];
            for(int i=1; i<=20; i++){
                if(mask&(1<<i)){
                    dp[mask][i] = dp[mask][i-1]+dp[mask^(1<<i)][i-1];
                }
                else dp[mask][i] = dp[mask][i-1];
            }
            //ans[mask] = dp[mask][N-1];
        }
        ll last = 0;
        for(int i=1; i<=n; i++){
            last += dp[(1<<N)-1-num[i]][N-1];
            tt[num[i]] = 0;
        }
        printf("%lld\n", last);
    }
    return 0;
}

题目2

题目链接

题解

寻找一个数，使得它们两的与运算为0
当我们要找num[i]时，我们需要的方案在dp[(1<<22)-1-num[i]]中
mask = (1<<22)-1-num[i]表示的是那些mask为0，则拓展的串必为0，mask为1的那些为拓展串可以为0或者1

例如我们要找num[i] = 1001 ,则mask=0110, 拓展串0000， 0010， 0100， 0110与num[i]进行与运算都为0

ac code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define ls (rt<<1)
#define rs (rt<<1|1)
#define mid (l+r>>1)
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define lowbit(x) (x&(-x))
#define inc(i, l, r) for(int i=l; i<=r; i++)
#define dec(i, r, l) for(int i=r; i>=l; i--)
const int inf = 0x3f3f3f3f;
const int maxn = 1e6+10;
const double pi = acos(-1.0);
const double eps = 1e-7;
const int mod = 1e9+7;
int readint()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
ll readll(){
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n, m;
int num[1<<22|1];
int dp[1<<22|1];
int tt[4000000+10];
int ans[4000000+10];
int nn[4000000+10];
int main()
{
    n=readint();
    cls(dp, -1);
    inc(i, 1, n) nn[i] = readint(), dp[nn[i]] = nn[i];
    for(int mask=0; mask<(1<<22); mask++){
        //dp[mask][0] = num[mask];
        //if(mask&1) if(dp[mask^1][0] !=-1) dp[mask][0] = dp[mask^1][0];
        for(int i=0; i<=21; i++){
            if(mask&(1<<i)){
                //if(dp[mask][i-1] != -1) dp[mask][i] = dp[mask][i-1];
                if(dp[mask^(1<<i)] != -1) dp[mask] = dp[mask^(1<<i)];
            }
            else{
                if(dp[mask] != -1) dp[mask] = dp[mask];
            }
        }
    }
    for(int i=1; i<=n; i++){
        printf("%d ", dp[(1<<22)-1-nn[i]]);
    }
    return 0;
}

未解决的问题

本文标题:SOS dp

文章作者:Babydragon

发布时间:2018-08-30, 12:53:51

最后更新:2018-08-30, 14:07:37

原始链接:http://baolintian.github.io/2018/08/30/SOS-dp/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. SOS dp解决的问题
  2. 2. special pairs
    1. 2.1. 题解
    2. 2.2. ac code
  3. 3. 题目2
    1. 3.1. 题解
    2. 3.2. ac code
  4. 4. 未解决的问题
{{ live2d() }}