题意:给定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 储能表”