建设网站英语,江苏建设教育,中文域名注册网站,龙岗高端网站建设正题
题目链接:https://www.luogu.com.cn/problem/P7740 题目描述
题目大意摸了
小 R 有 mmm#xff08;1≤m≤10001 \le m \le 10001≤m≤1000#xff09;个机器人和 mmm 张纸带#xff0c;第 iii#xff08;1≤i≤m1 \le i \le m1≤i≤m#xff09;个机器人负责对第 …正题
题目链接:https://www.luogu.com.cn/problem/P7740 题目描述
题目大意摸了
小 R 有 mmm1≤m≤10001 \le m \le 10001≤m≤1000个机器人和 mmm 张纸带第 iii1≤i≤m1 \le i \le m1≤i≤m个机器人负责对第 iii 张纸带进行操作。对于每张纸带它们都被从左到右分成了 nnn1≤n≤321 \le n \le 321≤n≤32个格子依次编号为 0,1,…,n−10, 1, \ldots , n - 10,1,…,n−1。每个格子有 333 种状态1. 格子上写有数字 0002. 格子上写有数字 1113. 格子是一个空格子。
在任意时刻机器人必须站在纸带上的一个格子中。在设定好机器人在纸带上的初始位置后第 iii 个机器人会依次执行预先设定的操作序列 SiS_iSi操作由 R、0、1、* 四种字符组成其中
R 表示机器人向右走一格如果右边没有格子则机器人会原地爆炸0 表示如果机器人所在格子非空则将该格子上的数字改为 000否则不修改1 表示如果机器人所在格子非空则将该格子上的数字改为 111否则不修改* 表示如果机器人所在格子非空则将格子上的数字 xxx 改为 1−x1 - x1−x否则不修改。
第 iii 张纸带的状态可以用一个长度为 nnn 的序列表示每个元素为 0、1 或 -空格子依次表示其每个格子的状态。第 iii 张纸带的初始状态称为机器人 iii 的输入 XiX_iXi操作执行完成后纸带的状态称为机器人 iii 的输出 YiY_iYi。注意如果机器人爆炸了那么这个机器人就没有输出。
可以发现如果一个格子为空那么机器人永远不会修改它。所以每个机器人都有如下特性如果第 iii 个机器人所在的纸带上的所有格子都为空那么它就不会执行任何操作它的输出即为所有格子都为空。
现在小 R 给定了每一个机器人的输入 XiX_iXi即每张纸带的初始状态以及目标输出 YiY_iYi。小 R 希望小 D 找到一个位置 ppp0≤pn0 \le p n0≤pn使得所有机器人都能以其所在纸带的第 ppp 个格子为初始位置在不爆炸的情况下执行完所有操作并且满足第 iii 个机器人的输出为 YiY_iYi。
小 D 花了几毫秒解决了问题现在他想知道有多少个输入和输出的组合方式使得上述问题有解即有多少种为每个机器人设定输入 X0,X1,…,Xm−1X_0, X_1, \ldots , X_{m - 1}X0,X1,…,Xm−1 和目标输出 Y0,Y1,…,Ym−1Y_0, Y_1, \ldots , Y_{m - 1}Y0,Y1,…,Ym−1 的方式使得至少存在一个位置 ppp0≤pn0 \le p n0≤pn使得所有机器人都能以其所在纸带的第 ppp 个格子为起点在不爆炸的情况下执行完所有操作且满足第 iii 个机器人的输出为 YiY_iYi。请你帮助小 D 解决这个问题由于最终的答案可能很大请你输出答案对 1097{10}^9 71097 取模后的余数。
两个组合方式不同当且仅当存在至少一个机器人它的输入或是目标输出在两个方式中不同。
对于所有测试点1≤n≤321 \le n \le 321≤n≤321≤m≤10001 \le m \le 10001≤m≤10001≤∣Si∣≤1001 \le \lvert S_i \rvert \le 1001≤∣Si∣≤100。
测试点编号n≤n \len≤m≤m \lem≤特殊限制1∼21 \sim 21∼2111111无333888111无444161616111无5∼65 \sim 65∼6323232111无777161616555无8∼108 \sim 108∼10323232555无11∼1211 \sim 1211∼12161616100010001000无13∼1513 \sim 1513∼15323232100010001000A16∼2116 \sim 2116∼21323232100010001000B22∼2522 \sim 2522∼25323232100010001000无
特殊限制 A操作序列中不存在 R。
特殊限制 B每个操作序列中R 的数量至多 151515 个。 解题思路
先考虑nnn比较小的情况。对于每个机器人我们可以把它的操作表示成相对于起点位置的4种状态必定为0/10/10/1与之前相同/不同。
然后至少有一个合法的xxx的限制我们可以考虑容斥钦定一些合法的位置那么对于纸带的一个位置来说它的限制最多只有四种我们对于不同的情况这个位置不同的起始状态对应同样数量的中止状态。
但是我们暴力枚举合法位置的复杂度是O(2n)O(2^n)O(2n)的考虑能不能优化。
因为这个n32n32n32看上去就很像折半所以我们考虑一下怎么折半。
我们会发现因为最大位置不能超出纸条所以设一个机器人最远的操作位置是lenlenlen那么对于这个机器人来说合法的xxx就不能超过n−lenn-lenn−len。而如果lenlenlen比较小那么一个位置能影响到后面的位置就不多我们可以设fi,Sf_{i,S}fi,S表示目前做到iii对于后面的限制目前是SSS时前面已经确定了限制的位置的答案。
然后所有的机器人同时做就可以了。
然后再处理限制的时候用bitsetbitsetbitset优化一下就行了。
时间复杂度O(2nnmω)O(\frac{2^nnm}{\omega})O(ω2nnm) code
#includecstdio
#includecstring
#includealgorithm
#includevector
#includebitset
#define ll long long
using namespace std;
const ll N34,M1100,P1e97;
ll n,m,pw2[M],pw3[M],v[M][N],c[M];
ll ans,num,f[N][117][2];
vectorll q[N];char s[N*3];
bitsetM all,v1,v2,u_[N],u[4][N],F[117][4];
signed main()
{scanf(%lld%lld,n,m);pw2[0]pw3[0]1;for(ll i1;im;i)pw2[i]pw2[i-1]*2ll%P,pw3[i]pw3[i-1]*3ll%P;for(ll i0;im;i){scanf(%s,s1);ll lenstrlen(s1),cr0;for(ll j1;jlen;j){if(s[j]R)v[i][c[i]]cr,cr0,c[i];else if(s[j]0)cr2;else if(s[j]1)cr3;else if(s[j]*)cr^1;}v[i][c[i]]cr;q[c[i]].push_back(i);all.set(i);}ans1;for(ll i1;in*m;i)ansans*3ll%P;for(ll rn;r0;r--){for(ll i0;iq[n-r].size();i){for(ll j0;jn2;j)u[v[q[n-r][i]][j]][j].set(q[n-r][i]);for(ll jc[q[n-r][i]]1;jn2;j)u_[j].set(q[n-r][i]);}f[0][0][0]1;numq[n-r].size();for(ll i1;ir;i){ll MS(1min(i,n-r1)),MT(1min(i-1,n-r1));for(ll s0;sMS;s)f[i][s][0]f[i][s][1]0;for(ll z0;z2;z)for(ll s0;sMT;s){ll _zz|(s*2MS);if(ir)(f[i][(s1)(MS-1)][_z]f[i-1][s][z])%P;(f[i][(s1|1)(MS-1)][_z]P-f[i-1][s][z])%P;}for(ll z0;z2;z){ll lrz|(ir);for(ll s0;smin(n-r1,i);s){for(ll jlr;j4;j)F[1s][j]u[j][s];if(!lr)F[1s][0]|u_[s];}for(ll s0;sMS;s){if(s!(s-s)){for(ll klr;k4;k)F[s][k]F[s-s][k]|F[s-(s-s)][k];}if(lr){v1F[s][1]|(F[s][2]F[s][3]);v2(F[s][2]|F[s][3])(v1^all);}else{v1(F[s][0]F[s][1])|(F[s][2]F[s][3]);v2(F[s][0]|F[s][1])(F[s][2]|F[s][3])(v1^all);}ll Xv1.count(),Yv2.count();(f[i][s][z]f[i][s][z]*pw2[Y]%P*pw3[num-X-Y]%P)%P;}}}ll limmin(n-r1,r),MS1lim;for(ll z0;z2;z)for(ll i1;in-r;i){for(ll s0;slim;s){for(ll jz;j4;j)F[1s][j]u[j][si];}for(ll s0;sMS;s){if(s!(s-s)){for(ll kz;k4;k)F[s][k]F[s-s][k]|F[s-(s-s)][k];}if(z){v1F[s][1]|(F[s][2]F[s][3]);v2(F[s][2]|F[s][3])(v1^all);}else{v1(F[s][0]F[s][1])|(F[s][2]F[s][3]);v2(F[s][0]|F[s][1])(F[s][2]|F[s][3])(v1^all);}ll Xv1.count(),Yv2.count();(f[r][s][z]f[r][s][z]*pw2[Y]%P*pw3[num-X-Y]%P)%P;}}for(ll z0;z2;z)for(ll s0;sMS;s)(ansP-f[r][s][z])%P;}printf(%lld\n,ans);return 0;
}
