有一个 n 行 m 列的表格，行从 0 到 n−1 编号，列从 0 到 m−1 编号。每个格子都储存着能量。最初，第 i 行第 j 列的格子储存着 (i xor j) 点能量。所以，整个表格储存的总能量是，\[\sum\limits_{i = 0} ^ {n - 1} \sum\limits_{j = 0} ^ {m - 1} (i \ {\rm xor} \ j)\] 随着时间的推移，格子中的能量会渐渐减少。一个时间单位，每个格子中的能量都会减少 1。显然，一个格子的能量减少到 0 之后就不会再减少了。 也就是说，k 个时间单位后，整个表格储存的总能量是，\[\sum\limits_{i = 0} ^ {n - 1} \sum\limits_{j = 0} ^ {m - 1} \max((i \ {\rm xor} \ j) - k, 0)\] 给出一个表格，求 k 个时间单位后它储存的总能量。 由于总能量可能较大，输出时对 p 取模。
http://www.lydsy.com/JudgeOnline/problem.php?id=4513 好难的数位DP啊...感觉网上并没有太好的题解，理解了好长时间... 我主要参考的题解：http://fancypei.github.io/2016/04/16/SDOI2016%20Round1/#排列计数 其实是数位DP的传统套路，按位进行讨论，讨论的时候，没有上限（下限）的时候可以枚举所有的0和1，但是之前的所有位到达上限（下限）的时候，就不能枚举了，只能和之前的一样，或者限制的值为1，可以枚举0（限制的值为0，可以枚举1）。 那么我们的状态设计就是： \(f[x][0/1][0/1][0/1]\)表示从最高位枚举到了第\(x\)位的全部有贡献的状态的结果和，第二维代表枚举值和\(n\)的关系，第三维表示枚举值和\(m\)的关系，第四维表示枚举值和\(k\)的关系，值为0，就代表之前的位还没有到达限制，这一位可以随便枚举，值为1，代表之前的位已经到达限制了，这一位需要被原有值的限制。 \(g[x][0/1][0/1][0/1]\)表示从最高位枚举到了第\(x\)位的全部有贡献的状态数，状态设计和上一个数组同理。 然后枚举上一位的状态\(a,b,c\)和这一位的数值\(xx,yy,zz\)，通过给定的这一位数值，来计算出这一位的状态\(aa,bb,cc\)。 对于方案数的状态转移非常简单，就是\[g[i][aa][bb][cc]+=g[i+1]_{abc}\] 对于结果的话，要计算出这一位对于结果的贡献，实际上，二进制的减法运算可以等效为列竖式的样子，各个位数的结果可以独立，到时候相加就可以了。 知道这个理论的话，方案的结果转移也比较简单\[f[i][aa][bb][cc]+=(zz-z)\times 2^i \times g[i+1]_{abc}\]
1 |
|