#include <cstdio>
#include <bitset>
#include <cstring>
#include <iostream>
using namespace std;
const int M = 1005;
const int N = 1<<16;
#define int long long
const int MOD = 1e9+7;
int read()
{
	int x=0,f=1;char c;
	while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
	while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}
int n,m,k,a[N],b[N],p2[M],p3[M];
int ans,f[N][2],g[N][2],dp[N],lg[N];
bitset<M> R,s1,s2,s3,in[M];
struct node
{
	bitset<M> b[4];
	node operator | (const node &v) const
	{
		node r;
		for(int i=0;i<4;i++) r.b[i]=b[i]|v.b[i];
		return r;
	}
	void set(int x,int y) {b[x].set(y);}
	int val()
	{
		s3=R&~((b[0]&b[1])|(b[2]&b[3]));
		s1=s3&(b[0]^b[1]);s2=s3&(b[2]^b[3]);
		int x=s1.count()+s2.count(),y=(s1&s2).count();
		return p2[y]*p3[x-2*y]%MOD;
	}
}h[M],t[N],Z;
void add(int &x,int y) {x=(x+y)%MOD;}
void work(int p)
{
	R=in[p];int L=1<<(n-p+1);
	memset(f,0,sizeof 0);f[0][0]=-1;
	for(int i=0;i<L;i++)
	{
		a[i]=t[i].val();
		node c9=t[i];c9.b[2].set();
		b[i]=c9.val();//sad
	}
	for(int j=1;j<=n;j++)
	{
		for(int i=0;i<L;i++) g[i][0]=g[i][1]=0;
		for(int i=0;i<L;i++)
		{
			int k=i<<1,w=k&(L-1),o=(k!=w),*z=(o?b:a);
			if(j!=p)//not choose
			{
				if(j<p) add(g[w][o],f[i][0]*b[w]);
				else add(g[w][o],f[i][0]*z[w]);
				add(g[w][1],f[i][1]*b[w]);
			}
			if(j<=p)//choose
			{
				w|=1;
				if(j<p) add(g[w][o],-f[i][0]*b[w]);
				else add(g[w][o],-f[i][0]*z[w]);
				add(g[w][1],-f[i][1]*b[w]);
			}
		}
		swap(f,g);
	}
	for(int i=0;i<L;i++)
		add(ans,f[i][0]+f[i][1]);
}
signed main()
{
	n=read();m=read();k=n/2;
	p2[0]=p3[0]=1;
	for(int i=1;i<=m;i++)
	{
		static char s[M]={};
		scanf("%s",s+1);Z.set(2,i);
		int w=2,len=0,t=strlen(s+1);
		p2[i]=p2[i-1]*2%MOD;
		p3[i]=p3[i-1]*3%MOD;
		for(int j=1;j<=t;j++)
		{
			if(s[j]=='R') h[len++].set(w,i),w=2;
			else if(s[j]=='*') w^=1;
			else w=s[j]-'0';
		}
		h[len].set(w,i);
		for(int j=1;j<=n;j++)
			if(len+j<=n) in[j].set(i);
		for(int j=len+1;j<=n;j++) h[j].set(2,i);
	}
	dp[0]=lg[0]=-1;
	for(int i=1;i<N;i++) lg[i]=lg[i>>1]+1;
	for(int i=1;i<(1<<k);i++) dp[i]=-dp[i&(i-1)];
	//p<=n/2
	for(int i=1;i<=n;i++)
	{
		for(int s=1;s<(1<<k);s++)
		{
			int d=i-lg[s&(-s)]-1;
			t[s]=t[s&(s-1)]|(d<0?Z:h[d]);
			R=in[lg[s]+1];
			dp[s]=dp[s]*t[s].val()%MOD;
		}
	}
	for(int s=1;s<(1<<k);s++) add(ans,dp[s]);
	//p>n/2
	for(int s=1;s<N;s++)
		t[s]=t[s&(s-1)]|h[lg[s&(-s)]];
	for(int i=k+1;i<=n;i++) work(i);
	printf("%lld\n",(ans+MOD)%MOD);
}

Solution

主播 vp 的时候一眼就会了这个题的 $O(nm 2^{\frac{n}{2}})$ 做法，稍微卡一会常就通过了本题。

似乎有很多可以优化的地方，不过它过了，我就不管了。场上写这个也无敌了吧。

容易把 $|S_i|$ 压缩到 $O(n)$ 量级。我们可以将 $S_i$ 看做：给 $p$ 之后的若干个位置进行用 $1$ 覆盖、用 $0$ 覆盖、翻转、保持不变四种状态之一。

考虑对 $p$ 的集合 $P$ 进行容斥，计算 $P$ 中所有点都是起点的方案数，乘上容斥系数 $(-1)^{|P|-1}$（注意钦定 $P \neq \varnothing$） 即可。

而对于每个位置，他都会被不同的 $p$ 用四种状态中的一些覆盖，可以算出 $(X_i,Y_i)$ 可能的对数，全部乘起来就行。

直接实现这个过程，可以获得 $16$ 分。特别的，如果所有机器人都移动了比较长的位置（比如 $>16$），那么实际上 $P$ 只有很少的位置有用（如果包含了 $>16$ 的位置，则放在上面的机器人都会爆炸，那么只能全空，相当于没用）。直接枚举。

当机器人移动步数比较小的时候，我们扫描整个纸带。发现只有非常少的位置是否在 $P$ 中是有用的。具体来说，我们先枚举 $P$ 中元素最大值是什么。这样可以清掉一些没用的机器人。对于剩下的机器人，可以直接把他们对于每一位的状态乘在一起。状压当前 $p$ 以及前 $15$ 个位置是否在 $P$ 集合中即可。

把上面两种做法拼在一起，复杂度为 $O(mn 2^{\frac{n}{2}})$。你需要稍微精细实现一下。

放一个很搞笑的代码：

#include<bits/stdc++.h>
#define ui unsigned int
#define ll long long
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
struct Mod
{
    ll m, p;
    void init(const int pp) { m = ((__int128)1 << 64) / pp; p = pp; }
	ll operator ()(const ll x)
    {
        return x - ((__int128(x) * m) >> 64) * p;
    }
} node;
using namespace std;
const int MAXN=1000+10,MOD=1e9+7;
int n,m,cnt[17],tmul[(1<<16)+1][2],Len[MAXN],del[MAXN];
string S[MAXN];
int get(vector<char> st) {
	int cov=-1,flp=0;
	for(auto ch:st) {
		if(ch=='0'||ch=='1') cov=ch-'0',flp=0;
		else if(ch=='*') {
			if(cov!=-1) cov^=1;
			else flp^=1;
		}
	}
	if(cov==1) return 1;
	if(cov==0) return 2;
	if(flp) return 3;
	return 4;
}

short MUL[(1<<16)+1][2][MAXN];
int MMul[(1<<16)+5][33],dp[33][(1<<17)+10];
inline int kmod(const int v) {return (v>=MOD)?v-MOD:v;}
int main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>m,node.init(MOD);
	ffor(i,1,m) cin>>S[i];
	ffor(o1,0,1) ffor(o2,0,1) ffor(o3,0,1) ffor(o4,0,1) {
		int v=8*o1+4*o2+2*o3+o4;
		if(o1&&o2||o3&&o4) cnt[v]=1;
		else if((o1||o2)&&(o3||o4)) cnt[v]=2;
		else if(o1||o2||o3||o4) cnt[v]=3;
		else cnt[v]=5;
	}
	ffor(i,0,(1<<16)-1) ffor(j,1,n) MMul[i][j]=1;
	ffor(i,1,m) {
		vector<char> st;
		vector<int> opt;
		for(auto ch:S[i]) {
			if(ch=='R') opt.push_back(get(st)),st.clear();
			else st.push_back(ch);
		}
		opt.push_back(get(st));
		if(opt.size()>n) {del[i]=1;continue ;}
		int len=n-opt.size()+1;
		Len[i]=len;
		if(len<=16) {
			ui t[40][4];
			t[0][0]=t[0][1]=t[0][2]=t[0][3]=0;
			ffor(j,0,n-1) {
				if(j<opt.size()) t[0][opt[j]-1]|=(1ll<<j);
				else t[0][3]|=(1ll<<j);
			}
			ffor(j,1,len-1) {
				t[j][0]=((t[j-1][0]&((1ll<<n-1)-1))<<1);
				t[j][1]=((t[j-1][1]&((1ll<<n-1)-1))<<1);
				t[j][2]=((t[j-1][2]&((1ll<<n-1)-1))<<1);
				t[j][3]=((t[j-1][3]&((1ll<<n-1)-1))<<1)|1;
			}
			ffor(s,0,(1<<len)-1) {
				int ns=0;
				ffor(j,0,len-1) if(s&(1<<j)) ns|=(1<<len-1-j);
				ui fin[4]={0,0,0,0};
				ffor(j,0,len-1) if(s&(1<<j)) fin[0]|=t[j][0],fin[1]|=t[j][1],fin[2]|=t[j][2],fin[3]|=t[j][3];
				ffor(j,0,n-1) {
					int tp=8*(!!(fin[0]&(1ll<<j)))+4*(!!(fin[1]&(1ll<<j)))+2*(!!(fin[2]&(1ll<<j)))+(!!(fin[3]&(1ll<<j)));
					MMul[ns][len]=node(1ll*MMul[ns][len]*cnt[tp]);
				}
			}
		}
		else {
			ui t[4]={0,0,0,0};
			ffor(j,0,n-1) if(j<opt.size()) t[opt[j]-1]|=(1ll<<j);
			else t[3]|=(1ll<<j);
			ffor(s,0,(1<<16)-1) ffor(o,0,1) {
				int f=((!!(s&t[0]))<<3)|((!!(s&t[1]))<<2);
				f|=((!!(s&t[2]))<<1)|((!!(s&t[3])))|o;
				MUL[s][o][i]=cnt[f];
			}
		}
	}
	ffor(i,0,(1<<16)-1) tmul[i][0]=tmul[i][1]=1;
	int ans=0;
	roff(lim,n,1) {
		dp[0][0]=-1;
		if(lim>16) ffor(i,1,m) if(!del[i]&&Len[i]>16&&lim==Len[i]) ffor(j,0,(1<<16)-1) 
			tmul[j][0]=node(1ll*tmul[j][0]*MUL[j][0][i]),
			tmul[j][1]=node(1ll*tmul[j][1]*MUL[j][1][i]);
		
		ffor(i,1,n) {
			int t=min(17,i-1),T=min(17,i);
			ffor(ls,0,(1<<T)-1) dp[i][ls]=0;
			ffor(ls,0,(1<<t)-1) if(dp[i-1][ls]) {
				int nls=(ls&(1<<16))|((ls&((1<<16)-1))<<1);
				if(i!=lim) dp[i][nls]=kmod(dp[i][nls]+dp[i-1][ls]);
				if(i<=lim) dp[i][nls|1]=kmod(dp[i][nls|1]+MOD-dp[i-1][ls]);
			}
			ffor(ls,0,(1<<T)-1) if(dp[i][ls]) {
				int us=(ls&((1<<16)-1)),v=(lim>i)|(!!(ls&(1<<16)));
				if(i<=16&&lim<=i) dp[i][ls]=node(1ll*dp[i][ls]*MMul[us][i]);
				dp[i][ls]=node(1ll*dp[i][ls]*tmul[us][v]);
			}
		}
		ffor(i,1,(1<<17)-1) ans=kmod(ans+dp[n][i]);
	}
	cout<<(ans%MOD+MOD)%MOD;
	return 0;
}