2022-team07-005

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

= 题解 =


* C:一种猜想；填aij时先默认填0，再通过Gauss计算行列式，如不可行则该填1.证明：注意到aij从0到1时 实际该变量为a[1..i-1][1..j-1]组成的行列式，而假设之前方案可行的情况下（数归），这是个奇数
故aij从0到1必可使对应行列式奇偶性改变，所以猜想成立。（后大表出来后经过@PM250的随手观察发现简单规律 PM250：加强加强）


* G: 注意到我们在构造字符串的时候，下一位仅需满足与原串中某几个位置不同（这几个位置满足构造串在以该位置结尾的后缀出现过）。于是我们据此构造一个压位dp，dp状态表示下一位需要满足与原串哪几个位置不同，这样便可写出一个O(2^25 * 4 * n) 的dp ，又注意到每次转移（下一位填什么字符）可以通过位运算加速 ，于是将复杂度压缩到 O（2^25 *4)。（dp数组可以用short卡空间）

题解

• C:一种猜想；填aij时先默认填0，再通过Gauss计算行列式，如不可行则该填1.证明：注意到aij从0到1时 实际该变量为a[1..i-1][1..j-1]组成的行列式，而假设之前方案可行的情况下（数归），这是个奇数

故aij从0到1必可使对应行列式奇偶性改变，所以猜想成立。（后大表出来后经过@PM250的随手观察发现简单规律 PM250：加强加强）

• G: 注意到我们在构造字符串的时候，下一位仅需满足与原串中某几个位置不同（这几个位置满足构造串在以该位置结尾的后缀出现过）。于是我们据此构造一个压位dp，dp状态表示下一位需要满足与原串哪几个位置不同，这样便可写出一个O(2^{25 * 4 * n) 的dp ，又注意到每次转移（下一位填什么字符）可以通过位运算加速 ，于是将复杂度压缩到 O（2}25 *4)。（dp数组可以用short卡空间）