题解(容斥)
2026-02-11 15:28:10
发布于:湖南
20阅读
0回复
0点赞
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
typedef unsigned long long ull;
const int P=1e9+7,N=35,B=65536,M=1005,L=105;
int h1,h2;
int n,m,mr,nr[M],ln[M],cnt[B];
int v[L];
char s[L];
int pw2[N],pw3[N];
ull mask[4],msk[B][4];//0:不变;1:变;2:为 0;3:为 1
ull emp[B],rct[B];//emp:必须为空的位置;rct:有限制的位置
int nw[B],f0[B];//nw:当前行状态为 S 的方案数;f0:所有行状态为 S 的方案数
int f1[N][B],f2[N][B];
//f1[i][S]:左半部分从右向左第 i个位置在它后面 i(包含它)个位置被选择的状态为 S时左半部分最右侧的点能够在操作后保持不变的方案数
//f2[i][S]:左半部分从右向左第 i个位置在它后面 i(包含它)个位置被选择的状态为 S时的总方案数
int g[2][B];//开个滚动数组,以免爆炸
inline int exminus(const int &a,const int &b) {int x=a-b;return x<0?x+P:x;}
inline int explus(const int &a,const int &b) {int x=a+b;return x<P?x:x-P;}
inline void Exminus(int &a,const int &b) {if((a-=b)<0) a+=P;}
inline void Explus(int &a,const int &b) {if((a+=b)>=P) a-=P;}
inline int mul2(int a) {Explus(a,a);return a;}
inline int mul3(int a) {Explus(a,mul2(a));return a;}
inline int get(ull S) {return cnt[S>>h1]+cnt[S&((1<<h1)-1)];}
inline int calc(int p) {
int res=0;
for(int S=0 ; S<(1<<p) ; ++S) if(S&1)
if(cnt[S]&1) Explus(res,f2[p][S]);
else Exminus(res,f2[p][S]);
for(int S=0 ; S<(1<<p) ; ++S) g[0][S]=0;
int t=0,ret=1;g[0][0]=1;
for(int i=0 ; i<=n-2*p ; ret=1ll*ret*f1[p][0]%P,++i,t^=1)
for(int S=0 ; S<(1<<p) ; ++S)
g[t^1][S]=1ll*exminus(g[t][S>>1],g[t][S>>1|(1<<(p-1))])*f1[p][S]%P;
Exminus(g[t][0],ret);
for(int i=n-2*p+1 ; i<n-p ; ++i,t^=1)
for(int S=0 ; S<(1<<p) ; ++S)
g[t^1][S]=1ll*exminus(g[t][S>>1],g[t][S>>1|(1<<(p-1))])*f1[p][S]%P;
for(int i=n-p ; i<n ; ++i,t^=1)
for(int S=0 ; S<(1<<p) ; ++S)
if((S&1)==(i==n-p)) g[t^1][S]=1ll*exminus(g[t][S>>1],g[t][S>>1|(1<<(p-1))])*f1[p][S]%P;
else g[t^1][S]=0;
for(int S=0 ; S<(1<<p) ; ++S)
if(cnt[S]&1) Explus(res,g[t][S]);
else Exminus(res,g[t][S]);
return res;
}
int main() {
freopen("robot.in","r",stdin);
freopen("robot.out","w",stdout);
scanf("%d%d",&n,&m);
h1=(n+1)>>1,h2=n-h1;
for(int S=0 ; S<(1<<h1) ; ++S) cnt[S]=cnt[S>>1]+(S&1);
for(int S=0 ; S<(1<<h1) ; ++S) f0[S]=1;
for(int i=1 ; i<=h2 ; ++i)
for(int S=0 ; S<(1<<i) ; ++S)
f1[i][S]=f2[i][S]=1;
pw2[0]=pw3[0]=1;
for(int i=1 ; i<=n ; ++i) pw2[i]=mul2(pw2[i-1]),pw3[i]=mul3(pw3[i-1]);
for(int o=0 ; o<m ; ++o) {
scanf("%s",s);
int len=strlen(s),p=0;
v[0]=0;
for(int i=0 ; i<len ; ++i)
if(s[i]=='R') v[++p]=0;
else if(s[i]=='0') v[p]=2;
else if(s[i]=='1') v[p]=3;
else v[p]^=1;
if((++p)>n) continue ;
for(int i=0 ; i<4 ; ++i) mask[i]=0;
for(int i=0 ; i<p ; ++i) mask[v[i]]|=1ull<<i;
int l=min(h1,n-p+1);
for(int S=0 ; S<(1<<l) ; ++S)
for(int i=0 ; i<4 ; ++i)
msk[S][i]=0;
for(int i=0 ; i<l ; ++i) {
for(int j=0 ; j<4 ; ++j) msk[1<<i][j]=mask[j]<<(l-1-i);
msk[1<<i][0]|=(1ull<<(l-1-i))-1;
msk[1<<i][0]|=(1ull<<n)-(1ull<<(l-1-i+p));
}
for(int S=0 ; S<(1<<l) ; ++S)
for(int j=0 ; j<4 ; ++j)
msk[S][j]=msk[S^(S&-S)][j]|msk[S&-S][j];
for(int S=0 ; S<(1<<l) ; ++S) {
emp[S]=(msk[S][0]&msk[S][1])|(msk[S][2]&msk[S][3]);
rct[S]=(msk[S][0]|msk[S][1])&(msk[S][2]|msk[S][3]);
rct[S]|=emp[S];
int c1=get(emp[S]),c2=get(rct[S]);
nw[S]=1ll*pw3[n-c2]*pw2[c2-c1]%P,f0[S]=1ll*f0[S]*nw[S]%P;
}
if(p>h2) continue ;
for(int i=p ; i<=h2 ; ++i)
for(int S=0 ; S<(1<<i) ; ++S)
f2[i][S]=1ll*f2[i][S]*nw[S]%P;
for(int S=0 ; S<(1<<h2) ; ++S) {
emp[S]|=msk[S][1];
rct[S]|=msk[S][1]|msk[S][2]|msk[S][3];
nw[S]=3-(rct[S]>>(h1-1)&1)-(emp[S]>>(h1-1)&1);
}
for(int i=p ; i<=h2 ; ++i)
for(int S=0 ; S<(1<<i) ; ++S)
f1[i][S]=1ll*f1[i][S]*nw[S]%P;
}
int res=0;
for(int S=1 ; S<(1<<h1) ; ++S)
if(cnt[S]&1) Explus(res,f0[S]);
else Exminus(res,f0[S]);
for(int i=1 ; i<=h2 ; ++i) Explus(res,calc(i));
printf("%d",res);
return 0;
}
全部评论 1
???
2026-02-11 来自 广东
0抱歉,我好像未写完(尴尬 ̄□ ̄||)
2026-02-11 来自 湖南
0












有帮助,赞一个