状压dp：Gym - 102832J

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133855597

https://vjudge.net/contest/587311#problem/G

认真读题，然后发现就是让区间不交，要么包含要么相离，长度为偶数，直接状压

状压就状压10位就行。转移发现长度为偶数，所以可能填法只有 252^5 。总复杂度 O(n215)O(n2^{15})

代码不长，就是有点难调

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
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){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<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
//mt19937 rand(time(0));
//mt19937_64 rand(time(0));
//srand(time(0));
#define N 2050
#define mo (int)(1e9+7)
void Add(int &a, int b) {
	a+=b; if(a>=mo || a<=-mo) a%=mo; 
    if(a<0) a+=mo; 
}
int n, m, i, j, k, T, p;
int f[N][N], blt[N<<5], fang[N], t, v[N<<2], s, ns, news; 
int mx; 

int work(int k) {
	int s1 = (k>>0)&1; 
	int s2 = (k>>1)&1; 
	int s3 = (k>>2)&1; 
	int s4 = (k>>3)&1; 
	int s5 = (k>>4)&1; 
	s1 <<= 1; 
	s2 <<= 3; 
	s3 <<= 5; 
	s4 <<= 7; 
	s5 <<= 9; 
	return s1|s2|s3|s4|s5; 
}

int lowbit(int x) {
	if(!x) return (1<<11); 
	return x&-x; 
}

signed main()
{
	n=read(); m=read(); 
	for(j=0, k=1; j<=12; ++j, k<<=1) blt[k]=j; 
	for(j=0; j<(1<<5); ++j) fang[j]=work(j); 
	for(i=1; i<=m; ++i) {
		p=read(); k=read(); 
		v[p-k]|=(1<<(2*k-1)); 
	}
	for(t=0; t<(1<<5); ++t) {
		if((fang[t]|v[0])!=fang[t]) continue;  
		f[0][fang[t]]=1; 
	}
	for(i=1; i<=n; ++i)
		for(s=0; s<(1<<10); ++s) {
			if((s|v[i-1])!=s) continue;  
			if(!f[i-1][s]) continue; 
			ns=(s>>1); 
			if(lowbit(ns)<lowbit(v[i]) && v[i]) continue; 
			mx=min(10ll, blt[lowbit(ns)]+1)>>1; 
			for(t=0; t<(1<<mx); ++t) {
				if((fang[t]|v[i])!=fang[t]) continue; 
				news=(ns|fang[t]); 
				Add(f[i][news], f[i-1][s]); 
			}
		}
	printf("%lld", f[n][0]); 
	return 0;
}