# BZOJ4513: [Sdoi2016]储能表(数位dp)

## Sol

f_{i,j}= \begin{aligned} i\oplus j &\left( i\oplus j >k\right) \\ 0 &\left( i\oplus j <=k\right) \end{aligned}

$\sum_{i=0}^{n - 1} \sum_{j = 0}^{m - 1} f(i, j) - k * \sum_{i = 0}^{n - 1} \sum_{j = 0}^{m - 1} [f(i, j)]$

$$f[len][0/1][0/1][0/1]$$表示此时到第$$len$$位，是否顶着$$n$$的上界，是否顶着$$m$$的上界，是否顶着$$k$$的下界

// luogu-judger-enable-o2
#include<bits/stdc++.h>
#define Pair pair<LL, LL>
#define MP make_pair
#define fi first
#define se second
#define LL long long
#define int long long
using namespace std;
const int MAXN = 233;
char c = getchar(); int x = 0, f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
LL N, M, K, mod, Lim, vis[MAXN][2][2][2];
Pair f[MAXN][2][2][2];
void add2(LL &x, LL y) {
if(x + y < 0) x = (x + y + mod);
else x = (x + y >= mod ? x + y - mod : x + y);
}
LL add(LL x, LL y) {
if(x + y < 0) return x + y + mod;
return x + y >= mod ? x + y - mod : x + y;
}
LL mul(LL x, LL y) {
return 1ll * x % mod * y % mod;
}
int Get(LL x) {
int len = 0; while(x) x >>= 1, len++; return len;
}
Pair dfs(int now, int f1, int f2, int f3) {
if(now > Lim) return MP(0, 1);
if(vis[now][f1][f2][f3]) return f[now][f1][f2][f3];
vis[now][f1][f2][f3] = 1;
Pair ans = MP(0, 0);
int L1 = (N >> Lim - now) & 1, L2 = (M >> Lim - now) & 1, L3 = (K >> Lim - now) & 1;
//cout << (f1 &&(!L1)) << endl;
for(int i = 0; i <= (f1 ? L1 : 1); i++) {
for(int j = 0; j <= (f2 ? L2 : 1); j++) {
if(f3 && ((i ^ j) < L3)) continue;
Pair nxt = dfs(now + 1, f1 && (i == L1), f2 && (j == L2), f3 && ((i ^ j) == L3));
}
}
return f[now][f1][f2][f3] = ans;
}
int solve() {
memset(vis, 0, sizeof(vis));
memset(f, 0, sizeof(f));
Lim = 0;
Lim = max(Get(N), max(Get(K), Get(M)));
Pair ans = dfs(1, 1, 1, 1);
}
signed main() {
for(int T = read(); T; T--, printf("%lld\n", solve()));
return 0;
}
/*
5000
504363800392059286 554192717354508770 21453916680846604 401134357
*/

0 条评论

• ### 逆元的三种解法(附详细证明)

友情提示： Latex加载稍慢，请耐心等待 什么是逆元？ 若x满足 我们称x是a在 意义下的逆元 逆元的基本解法 https://loj.ac/pr...

• ### 2017.10.25水题大作战题解

rank: ? T1P1615 西游记公司 https://www.luogu.org/problemnew/show/P1615 scanf直接秒 1 #i...

• ### 洛谷P1762 偶数(找规律)

https://www.luogu.org/problemnew/solution/P1762 Orz

• ### Vijos P1448 校门外的树【多解，线段树，树状数组，括号序列法+暴力优化】

校门外的树 描述 校门外有很多树，有苹果树，香蕉树，有会扔石头的，有可以吃掉补充体力的…… 如今学校决定在某个时刻在某一段种上一种树，保证任一时刻不会出现两段...

• ### 洛谷P1567 统计天数

题目背景 统计天数 题目描述 炎热的夏日，KC非常的不爽。他宁可忍受北极的寒冷，也不愿忍受厦门的夏天。最近，他开始研究天气的变化。他希望用研究的结果预测未来的天...

• ### leetcode周赛130 | 题解速递

leetcode周赛题解，后面每周如果有时间就做周赛题目，不单独发leetcode的题目了，做多了感觉都可以在以前的题目里面找到类似的。

• ### Android 自定义流布局。使用开源库SimpleFlowLayout

实际项目中需要实现一个 热门搜索 的栏目，类似下图： 由于 子项（子view) 中的文字是可变的，一行能显示的 子项 的个数也无法确定。需要支持自动换行和计算...

• ### 各种平衡树

记一下自己写的平衡树 方便以后复制粘贴 题目链接 Vector 最快：284ms 1 #include<cstdio> 2 #include<vector>...

• ### BZOJ1901: Zju2112 Dynamic Rankings(整体二分 树状数组)

给定一个含有n个数的序列a[1],a[2],a[3]……a[n]，程序必须回答这样的询问：对于给定的i,j,k，在a[i],a[i+1