2022-team07-004

从 Trac 迁移的文章

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

原文章内容如下：

= 题解 =


* B: 操作可转化为：将一个原数的p进制表示中的某一个非零位减一后得到新数。可以发现，如果这一轮选择原数的最高非零位进行操作得到新数，那么下一轮就只能选择新数进行操作（而不能选择原数）。所以必胜方必定可以通过每
一次都操作最高位，来保证每一轮数字的数码和（p进制表示下）减去1。故胜负只与原数p进制表示下的各位数码和的奇偶性相关。

* C: 位数不超过8位的数，直接将最高位前移一位 （特判0）；否则，交换最大的数字和最小的数字（特判数字全一样的数）

* E：换根dp解决

* G: 从{1 2}{2 3}开始递推，以它为左上角每次将其加上 k（该方阵阵级数）放到右边，将其复制一份放到右下角，将右上角方阵抑或1沿对角线对称到左下角即可

* H：简单概率，读懂题意就行

* I：先考虑一个最朴素的dp，然后显然可以用矩阵加速，但是发现复杂度仍然不太能接受。考虑到每次乘上的转移矩阵是一个只有主对角线和某一行为1的矩阵，所以可以直接手乘。

* J：直接调和级数筛法，再考虑一下重复问题

* K：枚举根号以内的因数即可

题解

• B: 操作可转化为：将一个原数的p进制表示中的某一个非零位减一后得到新数。可以发现，如果这一轮选择原数的最高非零位进行操作得到新数，那么下一轮就只能选择新数进行操作（而不能选择原数）。所以必胜方必定可以通过每

一次都操作最高位，来保证每一轮数字的数码和（p进制表示下）减去1。故胜负只与原数p进制表示下的各位数码和的奇偶性相关。

• C: 位数不超过8位的数，直接将最高位前移一位 （特判0）；否则，交换最大的数字和最小的数字（特判数字全一样的数）
• E：换根dp解决
• G: 从{1 2}{2 3}开始递推，以它为左上角每次将其加上 k（该方阵阵级数）放到右边，将其复制一份放到右下角，将右上角方阵抑或1沿对角线对称到左下角即可
• H：简单概率，读懂题意就行
• I：先考虑一个最朴素的dp，然后显然可以用矩阵加速，但是发现复杂度仍然不太能接受。考虑到每次乘上的转移矩阵是一个只有主对角线和某一行为1的矩阵，所以可以直接手乘。
• J：直接调和级数筛法，再考虑一下重复问题
• K：枚举根号以内的因数即可