CF79D

记录一下这道感觉非常神的 daily problem。讲思路。

下文 $1$ 表示亮，$0$ 表示不亮。

首先，操作到一个固定状态显然是比操作回全 $0$ 难做的。于是把操作逆过来。

如果我们直接按题目说的，区间反转入手，容易发现 $1$ 的个数大概率是越来越多的。怎么办呢？因为是区间操作，又是异或，于是想到将区间修改差分。

设 $b_i=a_i\oplus a_{i-1}$，问题就转换成：每次可以将 $b_i,b_{i+x_j}(i+x_j\le n+1)$ 两个位置异或上 $1$，问最少多少次操作后 $\forall i\in[1,n],b_i=0$。

考虑怎么解决一个问题。先思考：我们会凭空对两个为 $0$ 的位置操作吗？显然是不会的。但是又有一个问题：为什么不能用这次操作完产生的 $1$ 和其他位置再操作呢？这是因为差分操作可以无视顺序，所以交换顺序后，一定满足每次操作至少有一个位置的 $b_i=1$。

好的，现在这个问题已经被简单化很多了，但是两个位置同时异或 $1$ 这个操作仍然不好表示，于是考虑再把这个操作做一个转化。

考虑如果操作 $i,j$ 两个位置，$b_i=1,b_j=0$，可以怎么刻画呢？发现其实可以视作 $i$ 上的 $1$ 移动到了 $j$！如果两者都是 $1$ 呢？就可以视作 $i$ 上的 $1$ 移动到 $j$，并且和 $j$ 上的 $1$ 抵消了。

于是，我们可以将一次操作视为一个 $1$ 在一张图上走了一步，问最后每个点都能匹配上另一个点，使它们最后在同一个位置，或者这个点在 $n+1$ 号点。

由于 $\sum[b_i=1]\le2\times k\le20$，于是直接考虑状压 dp。预处理出 $i,j$ 位置上的 $1$ 最少需要几步相遇，然后每次枚举两个为 $1$ 的位置转移，最后加上移动到 $n+1$ 的贡献即可。

总结一下做法，每个 $i$ 向 $i+x_j,i-x_j$ 连边，用 $b_i=1$ 的位置做多源 bfs，最后状压 dp 求出两两匹配的最小操作次数。时间复杂度 $O(nl+2^{2k}k^2)$。

code：

int n,m,k,s,a[N],b[N],c[N],d[N],dis[27][N],f[27][27],dp[M];
int tot,head[N];
struct node{
	int to,nxt;
}e[N<<7];
il void add(int u,int v){
	e[++tot]={v,head[u]},head[u]=tot;
}
void bfs(int s,int j){
	queue<int> q;
	dis[j][s]=0,q.push(s);
	while(q.size()){
		int u=q.front();
		q.pop();
		go(i,u){
			int v=e[i].to;
			if(dis[j][v]<=dis[j][u]+1){
				continue;
			}
			dis[j][v]=dis[j][u]+1;
			q.push(v);
		}
	}
}
void Yorushika(){
	scanf("%d%d%d",&n,&m,&k);
	rep(i,1,m){
		int x;scanf("%d",&x);
		a[x]=1;
	}
	rep(i,1,k){
		scanf("%d",&c[i]);
	}
	rep(i,1,n){
		b[i]=a[i-1]^a[i];
		if(b[i]){
			d[++s]=i;
		}
		rep(j,1,k){
			if(i-c[j]>0){
				add(i,i-c[j]);
			}
			if(i+c[j]<=n+1){
				add(i,i+c[j]);
			}
		}
	}
	mems(dis,0x3f);
	rep(i,1,s){
		bfs(d[i],i);
	}
	rep(i,1,s){
		rep(j,i+1,s){
			if(i==j){
				continue;
			}
			f[i][j]=inf;
			rep(k,1,n){
				f[i][j]=min(f[i][j],dis[i][k]+dis[j][k]);
			}
		}
	}
	const int mx=1<<s;
	mems(dp,0x3f),dp[0]=0;
	int ans=inf;
	rep(S,0,mx-1){
		rep(i,1,s){
			rep(j,i+1,s){
				if(!(S>>(i-1)&1)||!(S>>(j-1)&1)){
					continue;
				}
				dp[S]=min(1ll*dp[S],1ll*dp[S^(1<<(i-1))^(1<<(j-1))]+f[i][j]);
			}
		}
		if(dp[S]>1e9){
			continue;
		}
		int sum=dp[S];
		bool fl=1;
		rep(i,1,s){
			if(!(S>>(i-1)&1)){
				if(dis[i][n+1]>1e9){
					fl=0;break;
				}
				sum+=dis[i][n+1];
			}
		}
		if(fl){
			ans=min(ans,sum);
		}
	}
	printf("%d\n",ans>1e9?-1:ans);
}
signed main(){
	int t=1;
	//	scanf("%d",&t);
	while(t--)
		Yorushika();
}