[数位DP][模板][二进制性质] SDOI2016 储能表

题目链接

题意:给定n, m, k, p, 求出
\[
\sum_{i=0}^{n-1}\sum_{j=0}^{m-1} max(i\oplus j-k)\\
最大数据范围
T = 5000, n \leq 10 ^ {18} , m \leq 10 ^ {18} , k \leq 10 ^ {18} , p \leq 10 ^ 9
\]

题解:转化成求\[\sum_{i=0}^{n-1}\sum_{j=0}^{m-1} i\oplus j*\epsilon(i\oplus j-k) – k*\sum_{i=0}^{n-1}\sum_{j=0}^{m-1} 1*\epsilon(i\oplus j-k)\],其中\[\epsilon(x)当x> 0时为1,否则为0\]. 这样的话可以直接数位dp计算了,有两个范围和一个约束,要计算的量也有两个,刚学到的kuangbin的板子十分的好用!!!这个甩锅给-1位的写法真的太简洁了。

error:第一个是搞错了当前位的贡献,只乘上了二进制位的权值,没有乘后面的种类数。第二个是爆int,日常long long错误
继续阅读“[数位DP][模板][二进制性质] SDOI2016 储能表”

[补题][数位dp][位运算] 2019牛客第七场 H Pair

题目链接

题意:给定ABC三个数,大小1e9,要求求出来1<=x<=A,1<=y<=B范围内满足(x&y)>C或(x^y)<C的(x,y)对数。

由于题目给的是或条件,所以还要考虑一个容斥的问题,先算出来单独满足两个条件的数目,再减去同时满足两个条件的数目,即可得到答案。先考虑单独计算两个条件的情况:

一般来说这种数位dp的框架都是类似的,在第i位时考虑前面的约束有没有“顶满”,如果顶满的话考虑当前这一位的限制,否则继续递归下去。这样的框架使得最后的递归边界处理变成了最有思维含量的一部分。这个题不同寻常的地方在于它是强制要求你同时考虑多个边界的,这是值得注意的一点。在这个题目里比较友好的一点是他对于与C的关系比对的时候是不等号,没有等号,这样的话,我们只要在dp计数的过程中一直保持可行性就可以了,到最后一步(pos=-1)只需要判断

1)前面是不是顶到C的头了,如果是的话就不行
2)前面是不是顶到了全0,因为题目要求x,y至少为1
继续阅读“[补题][数位dp][位运算] 2019牛客第七场 H Pair”