1 条题解
-
1
引言
相当于是旧题重做了。
上次做这题还是上次,下次做这题就是下次了。上次在真题记录一开始就开坑这题,直接寄飞;这次,在 题左右的训练之后,让我们重头开始。
当然 题中 dp 可能还不足一半。
思路
Version 1
考虑容斥。
我们对答案 集合的做子集容斥。
考虑怎么做。
暴力枚举 的集合的非空子集 ,然后对每个元素计算答案个数。
特别的,若答案为 个(爆炸了),则忽略当前机器人的贡献(空集贡献)。
复杂度 ,期望得分 。
如果优化一下,或许可以获得更高分数?
Version 2
考虑某些东西的答案对某些元素是本质相同的。
设 。
考虑一下,如果 中最左、最右元素距离不超过 ,则这样的 本质上只有 种;因为对于同样的平移过来的 ,对每个机器人而言,这部分答案在不爆炸时是定值。对每个机器人暴力计算这部分贡献。
如果 中最左、最右元素距离超过 ,则机器人本身运动路径长度不超过 ,考虑怎么利用这一点优化。
事实上,我们暴力枚举 ,并计算各部分贡献的过程,可以写成 的形式。
考虑怎么做。
由于路径比较短,每个起点 的状态必定只会显著地影响到接下来的路径长度数个元素,或者不显著地影响到距离长度外若干个元素(因为没走过的地方就是未变动的地方,相当于多了一条限制),因此我们只用记录对于当前位置而言,上 个位置是否有 中元素,以及再往前是否有 中元素,以及 中最远间距是否已经超过 ,以及是否已经结束选择,在这些条件下答案的带权方案数。
然后这个做法是有问题的,因为没有考虑到会不会机器人直接炸了,于是要改为暴力枚举最后一个起点,而不用记录“是否已经结束选择”这种东西。
转移的话是一次 的,压位优化一下可以做到 ,复杂度为 。
对于第一部分怎么优化?(直接枚举硬做是 的)
还是考虑压位,直接优化计算。复杂度 。
总复杂度为 。
Version 3
考虑继续优化算法。
考虑怎么做。
对于第一部分,我们可以直接递推出所有状态,而不用每次出现计算一遍,从而做到 。
当然,实际上暴力跑得很快,没必要继续卡常。缺点是这样子空间会很耗,静态空间至少需要 个
unsigned
,折合约 。因为优化太耗内存,且此过程实际效率已经比较高,根本卡不掉,我们暂且先不管这部分怎么继续优化。
考虑另外一部分怎么优化。
首先是常数。
注意到只有最后一步需要考虑 中最远间距是否已经超过 ,所以这个不用设入状态。
然后我们设枚举的终点是 ,则有效的元素其运动格子长度不会超过 。
于是只用记录对于当前位置而言,上 个位置是否有 中元素,以及再往前是否有 中元素,在这些条件下答案的带权方案数。
然后为了避免“ 中最远间距是否已经超过 ”无法统计,我们考虑人类智慧:先枚举到 ,再删去“到目前为止都未选取”的情况。这样,就可以避免问题了。
由于每次的复杂度为 ,总复杂度变为 。
然后就可以获得 loj 上 、Luogu 上 的好成绩。
甚至 loj 上开 Ofast 直接可过。考虑继续优化。
注意到形式如下频繁出现的代码段:
for(uint k=0,p;k<m;k++)if(cnt[p=Ord[k]]+endp<=n){ bol w0=op||(B[p][0]&(j<<1|1)),w1=B[p][1]&(j<<1|1),w2=B[p][2]&(j<<1|1),w3=B[p][3]&(j<<1|1); if(!((w0&&w1)||(w2&&w3)))v*=((w0||w1)&&(w2||w3))?2:3; }else break;
我们发现对固定的
op
,j
和endp
,这个v
所乘上的量是定值,直接开桶预处理即可。第二部分复杂度变为 ,但常数翻了 倍。
loj 上时间变为 ,Luogu 上变为 。
稍微卡卡常,变慢了。
使劲卡卡常,过了。
uoj 上也过了。
Code
经过精细卡常。
第一部分可以做到更优,但实际没必要。
复杂度可以做到 。
const ullt Mod=1e9+7; typedef ConstMod::mod_ullt<Mod>modint; typedef std::vector<modint>modvec; uint B[1005][4],cnt[1005],Ord[1005]; chr C[105];modint Pow2[55],Pow3[55]; modint Dp[33][1u<<16|1][2]; #define popcnt(v) __builtin_popcount(v) #define clz(v) __builtin_clz(v) int main() { #ifdef MYEE freopen("QAQ.in","r",stdin); // freopen("QAQ.out","w",stdout); #endif uint n,m;scanf("%u%u",&n,&m); Pow2[0]=Pow3[0]=1;for(ullt i=1;i<=n;i++)Pow2[i]=Pow2[i-1]*2,Pow3[i]=Pow3[i-1]*3; for(uint i=0;i<m;i++){ scanf("%s",C); uint&c=cnt[i]=0,op=0; for(chr*s=C;*s;s++) if(*s=='R')B[i][op]|=1u<<c++,op=0;else if(*s=='0')op=2; else if(*s=='1')op=3;else op=op^1; B[i][op]|=1u<<c++; for(uint j=c;j<n;j++)B[i][0]|=1u<<j; Ord[i]=i; } std::sort(Ord,Ord+m,[&](uint a,uint b){return cnt[a]<cnt[b];}); uint T=(n+1)/2;_min(T,n); modint ans; uint whole=n==32?-1:((1u<<n)-1); for(uint i=1;i<(1u<<T);i++)if(i&1){ uint bit=32-clz(i); std::vector<modint>V{1}; for(uint j=0;j<m;j++) { uint p=Ord[j],w[4]={0,0,0,0}; for(uint k=i,f;k;k-=f) f=lowbit(k), w[0]|=(f-1)|(f*B[p][0]),w[1]|=f*B[p][1], w[2]|=f*B[p][2],w[3]|=f*B[p][3]; uint A=(w[0]&w[1])|(w[2]&w[3]),B=(w[0]|w[1])&(w[2]|w[3]); A&=whole,B&=whole; V.push_back(V.back()*Pow2[popcnt(B&~A)]*Pow3[n-popcnt(B|A)]); } modint wil; for(uint i=0,j=m-1;i+bit<=n;i++) { while(~j&&bit+i+cnt[Ord[j]]>n+1)j--; wil+=V[j+1]; } (popcnt(i)&1)?ans+=wil:ans-=wil; } for(uint endp=T;endp<n;endp++){ std::vector<uint>W; for(uint k=0,p;k<m;k++)if(cnt[p=Ord[k]]+endp<=n)W.push_back(p);else break; uint All=(1u<<(n-endp))-1; static modint Chg[2][1u<<17|1]; static bol Done[2][1u<<17|1]; for(uint j=0;j<(1u<<(n-endp+1));j++)Done[0][j]=Done[1][j]=false; auto get=[&](bol op,uint j)->modint { if(Done[op][j])return Chg[op][j]; Done[op][j]=true; modint&v=Chg[op][j]=1; for(uint p:W){ bol w0=op||(B[p][0]&j),w1=B[p][1]&j,w2=B[p][2]&j,w3=B[p][3]&j; if(!((w0&&w1)||(w2&&w3)))v*=((w0||w1)&&(w2||w3))?2:3; } return v; }; for(uint i=0;i<=n;i++)for(uint j=0;j<=All;j++)for(uint op=0;op<2;op++) Dp[i][j][op]=0; Dp[0][0][0]=-modint(1); for(uint i=0;i<=endp-T;i++)for(uint j=0;j<=All;j++)for(uint op=0;op<2;op++)if(Dp[i][j][op]()) Dp[i+1][j<<1&All][op||(j>>(n-endp-1))]+=Dp[i][j][op]*get(1,j<<1), Dp[i+1][(j<<1|1)&All][op||(j>>(n-endp-1))]-=Dp[i][j][op]*get(1,j<<1|1); Dp[endp-T+1][0][0]=0; for(uint i=endp-T+1;i<endp;i++)for(uint j=0;j<=All;j++)for(uint op=0;op<2;op++)if(Dp[i][j][op]()) Dp[i+1][j<<1&All][op||(j>>(n-endp-1))]+=Dp[i][j][op]*get(1,j<<1), Dp[i+1][(j<<1|1)&All][op||(j>>(n-endp-1))]-=Dp[i][j][op]*get(1,j<<1|1); for(uint j=0;j<=All;j++)for(uint op=0;op<2;op++)if(Dp[endp][j][op]()) Dp[endp+1][(j<<1|1)&All][op||(j>>(n-endp-1))]-=Dp[endp][j][op]*get(op,j<<1|1); for(uint i=endp+1;i<n;i++)for(uint j=0;j<=All;j++)for(uint op=0;op<2;op++)if(Dp[i][j][op]()) Dp[i+1][(j<<1)&All][op||(j>>(n-endp-1))]+=Dp[i][j][op]*get(op,j<<1); for(uint j=0;j<=All;j++)for(uint op=0;op<2;op++)ans+=Dp[n][j][op]; } ans.println(); return 0; }
- 1
信息
- ID
- 140
- 时间
- 2000ms
- 内存
- 1024MiB
- 难度
- 10
- 标签
- 递交数
- 7
- 已通过
- 1
- 上传者