SOS dp

一类有关位运算的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;
}

未解决的问题

文章目录
  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() }}