题目详情 - [SDOI2016] 储能表 - BZOJ by HydroOJ
-
一道很好的数位 dp 题
-
不过这题有一个比较有意思的性质：当 \(n,m\) 为 \(2^k\) 的形式时，最终得到的数组对每一行排序后为 \(0 \sim m-1\) 的排列，如果有的话说不定可以作为一个部分分？
-
遇到二进制运算，通常不是按位考虑就是数位 dp 。这题按位考虑不现实，因为 \(> K\) 的约束条件比较严格，我们不能通过单纯的判断数位的某一位来知道这个数是否 \(> K\) ，因此我们考虑数位 dp
-
最终答案是什么？记 异或值 \(> K\) 的对数 \(S_1\) 和 异或值 \(> K\) 的异或和 \(S_2\) ，则最终答案为 \(S_2-S_1\times K\)
-
设计状态： \(f_{i,0/1,0/1,0/1}\) 表示考虑到第 \(i\) 位，\(n\) 的上界有没有取到、 \(m\) 的上界有没有取到、 \(K\) 的下界有没有取到的最终答案。再设一个辅助转移数组 \(g_{i,0/1,0/1,0/1}\) 定义相同，但记录的是对数。
-
初始化：\(f_{i,a,b,c}\leftarrow 0,g_{i,a,b,c}\leftarrow 0,g_{62,0,0,0}\leftarrow 1\)
-
转移：记下一维的状态为 \(a',b',c'\) ，第 \(i\) 位填的数为 \(zz\) ，\(K\) 的第 \(i\) 维为 \(z\)
-
\[\begin{align} g_{i+1,a,b,c} &\rightarrow g_{i,a',b',c'} \\ f_{i+1,a,b,c}+2^i \times (zz-z) \times g_{i+1,a,b,c} &\rightarrow f_{i,a',b',c'} \end{align} \]
-
最终答案： \(f_{0,0,0,0}\) ，因为下标是从 \(0\) 开始，所以前两项不用取到。因为异或和为 \(K\) 的会被减掉，因此不用考虑 \(\leq K\) 的情况，第三项不用取到
-
-
最终复杂度 \(O(T \log n)\)