链接:https://www.luogu.com.cn/problem/P7740
题目描述：有 \(m\) 个机器人和 \(m\) 张纸袋，每个纸袋有 \(n\) 个格子，每个格子可能是空，写有数字 \(0\) 或写有数字 \(1\) 。每一个机器人有一个操作序列，操作序列的每个字符均为 \(R,0,1,*\) 之一。
其中:
\(R\) 表示机器人向右走一格(如果右边没有格子，则机器人会原地爆炸)；\(0\) 表示如果机器人所在格子非空，则将该格子上的数字改为 \(0\)，否则不修改；\(1\) 表示如果机器人所在格子非空，则将该格子上的数字改为 \(1\)，否则不修改；$* $表示如果机器人所在格子非空，则将格子上的数字 \(x\) 改为 \(1-x\)，否则不修改。
我们称第 \(i\) 张纸带的初始状态称为机器人 \(i\) 的输入 \(X_{i}\) ，操作执行完成后纸带的状态称为机器人\(i\)的输出\(Y_{i}\)。若 \(X_{i}\) 均为空，则机器人 \(i\) 不会执行任何操作。你需要求出有多少种本质不同的每个机器人设定输入 \(X_{0},X_{1},...,X_{m-1}\) 和目标输出的方式 \(Y_{0},Y_{1},...,Y_{m-1}\) 满足其存在一个\(p\)使得所有机器人都能以其所在纸带的第 \(p\) 个格子为起点,在不爆炸的情况下执行完所有操作，且满足第 \(i\) 个机器人的输出为 \(Y_{0},Y_{1},...,Y_{m-1}\)，请输出答案对\(10^9+7\)取模的结果。
题解：注意到 \(n\leq 32\) ，考虑子集容斥。
考虑每一个机器人进行操作带来的影响，则对于一个输入 \(A\) ，对于输出 \(B\) ，要么 \(B_{i}=0\)，要么 \(B_{i}=1\)，要么 \(B_{i}=1-A_{i}\)，要么 \(B_{i}=A_{i}\)。注意到它其实确定了 \(A,B\) 之间的一些关系。我们定义一个运算域，将其设为数 \((?,0)\)，\((?,1)\)，\((x,x)\)，\((x,1-x)\)，定义合并运算符 \(*\)。
则其进行运算可以得到 \((?,?)\)，\((0,0)\)，\((0,1)\)，\((1,0)\)，\((1,1)\)，\((?,0)\)，\((?,1)\)，\((x,x)\)，\((x,1-x)\)，(不合法) \(10\) 种数。
将运算关系列出下表：
\(*\) \(0\) \(1\) \(2\) \(3\) \(4\) \(5\) \(6\) \(7\) \(8\) \(9\)
\(0\) \(0\) \(1\) \(2\) \(3\) \(4\) \(5\) \(6\) \(7\) \(8\) \(9\)
\(1\) \(1\) \(1\) \(9\) \(9\) \(9\) \(1\) \(9\) \(1\) \(9\) \(9\)
\(2\) \(2\) \(9\) \(2\) \(9\) \(9\) \(9\) \(2\) \(9\) \(2\) \(9\)
\(3\) \(3\) \(9\) \(9\) \(3\) \(9\) \(3\) \(9\) \(9\) \(3\) \(9\)
\(4\) \(9\) \(9\) \(9\) \(4\) \(9\) \(4\) \(4\) \(9\) \(9\) \(9\)
\(5\) \(5\) \(5\) \(9\) \(3\) \(9\) \(5\) \(9\) \(5\) \(3\) \(9\)
\(6\) \(6\) \(9\) \(2\) \(9\) \(4\) \(9\) \(6\) \(4\) \(2\) \(9\)
\(7\) \(7\) \(1\) \(9\) \(9\) \(4\) \(1\) \(4\) \(7\) \(9\) \(9\)
\(8\) \(8\) \(9\) \(2\) \(3\) \(9\) \(3\) \(2\) \(9\) \(8\) \(9\)
\(9\) \(9\) \(9\) \(9\) \(9\) \(9\) \(9\) \(9\) \(9\) \(9\) \(9\)
可以发现该表中\(9*x=9\)，\(0*x=x\)，且\(0\)，\(1\)，\(2\)，\(3\)，\(4\)，\(9\)可以形成一个独立的运算域，\(1\)，\(2\)，\(3\)，\(4\)任意两个\(*\)起来均为\(9\)。那么我们可以猜想其与或运算一一对应，即将 \(9\) 看成 \(1111\)，\(0\) 看成 \(0000\)，\(1\) 看成 \(1110\)，\(2\) 看成 \(1011\)，\(3\) 看成 \(0111\)，\(4\) 看成 \(1101\)，那么可将 \(6\) 看成 \(0110\)，\(7\) 看成 \(1001\)，\(8\) 看成 \(1100\)，\(9\) 看成 \(0011\)，经检验可以发现其的确满足条件。而最终每一个数的权值则可以写为 \(popcnt_{0}(x)+1\)。可将每个机器人从每个位置开始的操作序列压成一个 \(\texttt{unsigned int 128}\)，令第\(i\)个机器人的从第\(j\)个位置开始的组成的数形成的 \(\texttt{unsigned int 128}\)为\(f_{i,j}\),则每个 \(\texttt{unsigned int 128}\)的贡献\(F\)为每四位的权值之积。
经上述转化，原问题转化为了求 \(\sum_{S}(-1)^{|S|}\prod_{i=1}^{m}F(|_{j\in S}f_{i,j})\)。可以通过预处理 \([0,16^k]\) 的 \(F\) 做到 \(O(m2^nn/k+2^nn)\)。
再考虑 \(n≤32\) 且 \(R\) 个数仅有\(15\)的情况，考虑 \(dp\) 哪些 \(p\) 被选到了。注意到对于大多数情况 \(|_{jbelong S}f_{i,j}\) 上每\(4\)位的贡献状态只由其前 \(15\) 个位置是否选择确定，但存在不 \(|1100\) 的位与爆炸情况，但注意到若 \(p\) 的最小值 \(l\) 与最大值 \(r\) 若确定，则爆炸与是否额外 \(|1100\) 的状态是确定的，即当 \(l+len\leq r\) 时其不会 \(|1100\),\(r+len-1>n\) 时其会爆炸，可做到 \(O(m2^{15}+2^{15}n^3)\)。
考虑拼和两算法，令 \(Base=\frac{n+1}{2}\),注意到 \(len>Base\) 时 \(r-l+1\) 很小，可以用算法 \(1\) ， \(len\leq Base\) 时可以状压。而不 \(|1100\) 的情况只会在 \(r-l+1\) 小的时候出现，通过按 \(r-l+1\) 与 \(Base\) 的大小关系分类可以减少细节。当 \(r-l+1>Base\) 时，若 \(l+len\leq r\) 即可均 \(|1100\) ，此时因\(len\leq n-Base+1,Base\geq n-Base\)有\(l+len\leq r\)。而爆炸只与\(r\)相关，因此采用倒序 \(dp\) 记录未来状态的方式可以将算法\(2\)的复杂度优化至 \(O(m2^{Base}+2^{Base}n^2)\)。
因此总复杂度为 \(O(m2^{n/2}n/k+2^{n/2}n^2+16^k)\)，\(k\) 取 \(5\) 可以通过。
#include<iostream>
#include<cstdio>
#define M 1000
#define int long long
#define mod 1000000007
#define N 33
#define BASE 16
#define LENGTH 1048576
using namespace std;
typedef unsigned __int128 u128;
int read()
{
char c=0;
int sum=0;
while (c<'0'||c>'9') c=getchar();
while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
return sum;
}
int n,m,Base,F[M+1][N+1],pw3[N*M+1],len[M+1],SZ[1<<BASE],G[N+1][1<<BASE],H[N+1][1<<BASE],sz[N+1],dp[N+1][1<<BASE],ans,g[1<<4],lg[1<<BASE],st[1<<BASE],sg[LENGTH+1];
u128 S[M+1][N+1],pw2[4*N+1],ST[1<<BASE],skt;
string s[M+1];
int lowbit(int x)
{
return x&(-x);
}
signed main()
{
n=read(),Base=(n+1)/2,m=read();
for (int i=1;i<=m;++i) cin>>s[i];
g[0]=5,SZ[0]=-1,pw3[0]=pw2[0]=sg[0]=1;
for (int i=1;i<(1<<4);++i) g[i]=g[i-lowbit(i)]-1;
for (int i=1;i<=LENGTH;++i) sg[i]=sg[i/16]*g[i%16];
for (int i=1;i<(1<<Base);++i) SZ[i]=-SZ[i-lowbit(i)];
for (int i=1;i<=n*m;++i) pw3[i]=pw3[i-1]*3%mod;
for (int i=1;i<=4*n;++i) pw2[i]=pw2[i-1]*2;
for (int l=1;l<=n;++l)
for (int t=0;t<(1<<min(n-l+1,Base));++t)
G[l][t]=1;
for (int i=1;i<=n;++i)
for (int t=0;t<(1<<Base);++t)
H[i][t]=1;
lg[0]=-1;
for (int i=1;i<=(1<<Base);++i) lg[i]=lg[i/2]+1;
for (int i=1;i<=m;++i)
{
for (int j=1;j<=n;++j) F[i][j]=12;
len[i]=1;
for (int j=0;j<s[i].length();++j)
{
if (s[i][j]=='R') len[i]=min(len[i]+1,n+1);
if (s[i][j]=='0') F[i][len[i]]=6;
if (s[i][j]=='1') F[i][len[i]]=9;
if (s[i][j]=='*') F[i][len[i]]=15-F[i][len[i]];
}
for (int j=1;j<=n;++j) S[i][1]=S[i][1]*16+F[i][j];
for (int j=2;j<=n;++j) S[i][j]=S[i][j-1]/16+12*pw2[4*n-4];
for (int t=1;t<(1<<Base);++t)
{
ST[t]=ST[t-lowbit(t)]|S[i][lg[lowbit(t)]+1];
if (t&1)
{
skt=ST[t];
while (skt) G[len[i]][t]=G[len[i]][t]*sg[skt%LENGTH]%mod,skt/=LENGTH;
}
}
st[0]=12;
for (int t=0;t<(1<<Base);++t) st[t]=st[t-lowbit(t)]|F[i][lg[lowbit(t)]+1],H[len[i]][t]=H[len[i]][t]*g[st[t]]%mod;
sz[len[i]]=sz[len[i]]+1;
}
for (int i=2;i<=n;++i)
{
sz[i]=(sz[i]+sz[i-1])%mod;
for (int t=0;t<(1<<Base);++t) H[i][t]=H[i][t]*H[i-1][t]%mod;
for (int t=0;t<(1<<Base);++t) G[i][t]=G[i][t]*G[i-1][t]%mod;
}
for (int l=1;l<=n;++l)
for (int t=0;t<(1<<min(n-l+1,Base));++t)
if (t&1)
ans=(ans+SZ[t]*G[n+1-l-lg[t]][t]%mod)%mod;
for (int r=1;r<=n;++r)
{
for (int l=1;l<=n;++l)
for (int t=0;t<(1<<min(l,Base));++t)
dp[l][t]=0;
for (int t=0;t<(1<<Base);++t)
{
bool op=0;
for (int k=0;k<Base;++k)
if (((1<<k)&t)&&n-k>r)
op=1;
if (!op) dp[n][t]=H[n-r+1][t]*SZ[t]%mod;
}
for (int l=n;l>=2;--l)
{
if (l==r)
{
for (int t=0;t<(1<<min(l,Base));++t)
if (!(t&1))
dp[l][t]=0;
}
for (int t=0;t<(1<<min(l,Base));++t)
{
if (l>=Base+1&&l-Base<=r) dp[l-1][t/2+(1<<(Base-1))]=(dp[l-1][t/2+(1<<(Base-1))]-dp[l][t]*H[n-r+1][t/2+(1<<(Base-1))]%mod)%mod;
dp[l-1][t/2]=(dp[l-1][t/2]+dp[l][t]*H[n-r+1][t/2]%mod)%mod;
}
}
for (int l=1;l<=r-Base;++l) ans=(ans+dp[l][1]*pw3[(l-1)*sz[n-r+1]]%mod)%mod;
}
printf("%lld\n",(ans+mod)%mod);
return 0;
}