考虑容斥，令$f(S)$为要求$forall pin S,p$可以作为起点的方案数，答案即$sum_{Ssubseteq[0,n)}(-1)^{|S|}f(S)$
关于计算$f(S)$，对于第$i$个机器人而言，$p$可以作为起点实际上即给出了$X_{i}$和$Y_{i}$每一位上的一种限制，限制共有四种（令两者分别为$x$和$y$，即$y=0,y=1,x=y$和$x
e y$）
对每种限制预处理出第$i$个机器人以$p$为起点第$j$位上是否存在该限制，并用unsigned int存储，即可$o(n)$合并限制，进而对每一个位置分别求出满足此限制下的方案数，全部相乘即为$f(S)$
（另外需要注意如果会超出范围，仍存在全为空位的一组解）
预处理复杂度为$o(n^{2}m)$，求$f(S)$的复杂度为$o(nm)$，时间复杂度为$o(nm2^{n})$，无法通过
进一步的，预处理出子集并，再简单分类讨论即可快速求出方案数（一个unsigned int的2的位数可以将其前后的16位拆开分别处理），时间复杂度降为$o(m2^{n})$，仍无法通过
考虑优化，设第$i$个机器人有$r_{i}$个’R’，那么若$r_{i}+max_{xin S}xge n$即会导致其对答案没有贡献
接下来，考虑暴力枚举$max_{xin S}x$并对其分类讨论：
1.若$max_{xin S}x<lceilfrac{n}{2}ceil$，直接暴力枚举$S$即可，时间复杂度为$o(m2^{frac{n}{2}})$
2.若$max_{xin S}xge lceilfrac{n}{2}ceil$，那么若$r_{i}+xge n$其对答案也没有贡献，不需要考虑
换言之，此时即有$0le r_{i}<x$，那么一个位置对答案是否有贡献仅取决于其之前$x$个格子的起点状态以及再之前是否存在起点（即要求相同）
由此，记录这些状态即可状压dp，通过预处理也可以做到$o((n^{2}+m)2^{frac{n}{2}})$
综上，总复杂度为$o((n^{2}+m)2^{frac{n}{2}})$，可以通过
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N 35 4 #define M 1005 5 #define L (1<<16) 6 #define mod 1000000007 7 #define inv2 500000004 8 #define inv3 333333336 9 #define inv5 400000003 10 #define ll long long 11 #define ui unsigned int 12 int n,m,R,nn,ans,mi2[N],mi3[N],cnt[L],r[M]; 13 char s[105]; 14 ui o=1,lim[M][N][4],Lim[L][4]; 15 int lowbit(int k){ 16 return (k&(-k)); 17 } 18 void get(int k){ 19 int nn=(n+1>>1); 20 for(int i=0;i<nn;i++)memcpy(Lim[1<<i],lim[k][i],sizeof(lim[k][i])); 21 for(int S=1;S<(1<<nn);S++) 22 for(int i=0;i<4;i++)Lim[S][i]=(Lim[lowbit(S)][i]|Lim[S^lowbit(S)][i]); 23 } 24 namespace Subtask1{ 25 int sum[L]; 26 int count(ui k){ 27 return cnt[k>>16]+cnt[k&(L-1)]; 28 } 29 void calc(){ 30 nn=(n+1>>1); 31 for(int S=1;S<(1<<nn);S++)sum[S]=1; 32 for(int i=1;i<=m;i++){ 33 get(i); 34 for(int S=1;S<(1<<min(n-r[i],nn));S++){ 35 ui p0=Lim[S][0],p1=Lim[S][1]; 36 ui p2=Lim[S][2],p3=Lim[S][3]; 37 ui P0=((p0&p1)|(p2&p3)); 38 if (n<32)P0^=(o<<n)-1; 39 else P0^=(ui)(-1); 40 ui P1=((p0|p1)&(p2|p3)&P0); 41 sum[S]=(ll)mi2[count(P1)]*mi3[count(P0^P1)]%mod*sum[S]%mod; 42 } 43 } 44 for(int S=1;S<(1<<nn);S++) 45 if (cnt[S]&1)ans=(ans+sum[S])%mod; 46 else ans=(ans-sum[S]+mod)%mod; 47 } 48 } 49 namespace Subtask2{ 50 int id[M],g[L][2],f[2][L][2]; 51 bool cmp(int x,int y){ 52 return r[x]<r[y]; 53 } 54 void calc(){ 55 for(int i=1;i<=m;i++)id[i]=i; 56 sort(id+1,id+m+1,cmp); 57 nn=(n>>1); 58 for(int S=0;S<(1<<nn);S++)g[S][0]=g[S][1]=1; 59 for(int x=n-1,k=1;x>=n-nn;x--){ 60 while ((k<=m)&&(r[id[k]]+x<n)){ 61 get(id[k]); 62 for(int S=0;S<(1<<nn);S++){ 63 int p0=((Lim[S][0]>>nn-1)&1),p1=((Lim[S][1]>>nn-1)&1); 64 int p2=((Lim[S][2]>>nn-1)&1),p3=((Lim[S][3]>>nn-1)&1); 65 if ((p0&p1)||(p2&p3))continue; 66 if ((p0|p1)&&(p2|p3))g[S][0]=2*g[S][0]%mod; 67 else{ 68 if (p0|p1|p2|p3)g[S][0]=3LL*g[S][0]%mod; 69 else g[S][0]=5LL*g[S][0]%mod; 70 } 71 p2=1; 72 if ((p0&p1)||(p2&p3))continue; 73 if ((p0|p1)&&(p2|p3))g[S][1]=2*g[S][1]%mod; 74 else g[S][1]=3LL*g[S][1]%mod; 75 } 76 k++; 77 } 78 memset(f[0],0,sizeof(f[0])); 79 f[0][0][0]=1; 80 for(int i=0;i<x;i++){ 81 int ii=(i&1); 82 memset(f[ii^1],0,sizeof(f[ii^1])); 83 for(int S=0;S<(1<<nn);S++){ 84 int p=(S&1),SS=(S>>1); 85 f[ii^1][SS][p]=(f[ii^1][SS][p]+(ll)g[SS][1]*f[ii][S][0])%mod; 86 f[ii^1][SS][1]=(f[ii^1][SS][1]+(ll)g[SS][1]*f[ii][S][1])%mod; 87 SS|=(1<<nn-1); 88 f[ii^1][SS][p]=(f[ii^1][SS][p]-(ll)g[SS][1]*f[ii][S][0]%mod+mod)%mod; 89 f[ii^1][SS][1]=(f[ii^1][SS][1]-(ll)g[SS][1]*f[ii][S][1]%mod+mod)%mod; 90 } 91 } 92 for(int S=0;S<(1<<nn);S++){ 93 int p=(S&1),SS=((S>>1)|(1<<nn-1)),s=f[x&1][S][0]; 94 for(int j=x;j<n;j++){ 95 s=(ll)s*g[SS][p]%mod; 96 p|=(SS&1),SS>>=1; 97 } 98 ans=(ans+s)%mod; 99 SS=((S>>1)|(1<<nn-1)),s=f[x&1][S][1]; 100 for(int j=x;j<n;j++){ 101 s=(ll)s*g[SS][1]%mod; 102 SS>>=1; 103 } 104 ans=(ans+s)%mod; 105 } 106 } 107 } 108 } 109 int main(){ 110 mi2[0]=mi3[0]=1; 111 for(int i=1;i<N;i++){ 112 mi2[i]=2*mi2[i-1]%mod; 113 mi3[i]=3LL*mi3[i-1]%mod; 114 } 115 for(int i=1;i<L;i++)cnt[i]=cnt[i^lowbit(i)]+1; 116 scanf("%d%d",&n,&m); 117 for(int i=1;i<=m;i++){ 118 scanf("%s",s); 119 for(int j=0;s[j];j++) 120 if (s[j]=='R')r[i]++; 121 for(int j=0;j<n-r[i];j++){ 122 for(int k=0;k<j;k++)lim[i][j][2]|=(o<<k); 123 for(int k=j+r[i]+1;k<n;k++)lim[i][j][2]|=(o<<k); 124 int pos=j,lst=2; 125 for(int k=0;s[k];k++){ 126 if (s[k]=='R'){ 127 lim[i][j][lst]|=(o<<pos); 128 pos++,lst=2; 129 } 130 else{ 131 if (s[k]=='*')lst^=1; 132 else lst=s[k]-'0'; 133 } 134 } 135 lim[i][j][lst]|=(o<<pos); 136 } 137 } 138 Subtask1::calc(); 139 Subtask2::calc(); 140 printf("%d ",ans); 141 return 0; 142 }
View Code