2020-2021:teams:legal_string:组队训练比赛记录:contest16
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:组队训练比赛记录:contest16 [2021/08/26 16:38] jxm2001 |
2020-2021:teams:legal_string:组队训练比赛记录:contest16 [2021/08/28 08:50] (当前版本) jxm2001 [题解] |
||
|---|---|---|---|
| 行 10: | 行 10: | ||
| | E | 0 | 0 | 0 | | | E | 0 | 0 | 0 | | ||
| | G | 2 | 1 | 0 | | | G | 2 | 1 | 0 | | ||
| - | | I | 2 | 0 | 0 | | + | | I | 2 | 1 | 0 | |
| | J | 2 | 0 | 2 | | | J | 2 | 0 | 2 | | ||
| | K | 2 | 1 | 0 | | | K | 2 | 1 | 0 | | ||
| 行 1442: | 行 1442: | ||
| 显然根据 $a,b,s$ 奇偶性以及预处理组合数可以 $O(1)$ 计算 $h(a,b,s)$。 | 显然根据 $a,b,s$ 奇偶性以及预处理组合数可以 $O(1)$ 计算 $h(a,b,s)$。 | ||
| - | 然后总移动方案为 $h(a,1,s)$。利用容斥，首先我们减去非法序列为 ''L+.*'' 和 ''R+.*'' (非法序列均用正则表达式表示)的移动方案。 | + | 然后总移动方案为 $h(a,1,s)$。利用容斥，首先我们减去非法序列为 ''.*L+.*'' 和 ''.*R+.*'' (非法序列均用正则表达式表示)的移动方案。 |
| - | 设 $l(x)=-x,r(x)=2(n+1)-x$。根据简单组合数学知识，不难发现 ''L+.*'' 代表的方案为 $h(a,l(1),s)$，''R+.*'' 代表的方案为 $h(a,r(1),s)$。 | + | 设 $l(x)=-x,r(x)=2(n+1)-x$。 |
| - | 接下来我们需要补上减去非法序列为 ''L+R+.*'' 和 ''R+L+.*'' 的移动方案，分别为 $h(a,r(l(1)),s),h(a,l(r(1)),s)$。依次类推，有 | + | 根据简单组合数学知识，不难发现 ''.*L+.*'' 代表的方案为 $h(a,l(1),s)$，''.*R+.*'' 代表的方案为 $h(a,r(1),s)$。 |
| + | |||
| + | 接下来我们需要补上减去非法序列为 ''.*L+R+.*'' 和 ''.*R+L+.*'' 的移动方案，分别为 $h(a,r(l(1)),s),h(a,l(r(1)),s)$。 | ||
| + | |||
| + | 依此类推，有 | ||
| $$ | $$ | ||
2020-2021/teams/legal_string/组队训练比赛记录/contest16.1629967139.txt.gz · 最后更改: 2021/08/26 16:38 由 jxm2001
