专栏首页数据结构与算法BZOJ4513: [Sdoi2016]储能表(数位dp)

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

题意

题目链接

Sol

一点思路都没有,只会暴力,没想到标算是数位dp??Orz

首先答案可以分成两部分来统计

\[ 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)]\]

也就是说,我们要统计出满足条件的数的异或和以及满足条件的数的对数

考虑直接在二进制下数位dp,注意这里我们要记三维状态

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

然后直接dp就可以了

// 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;
inline LL read() {
    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));
            add2(ans.se, nxt.se);
            add2(ans.fi, add(nxt.fi, mul(nxt.se, mul((i ^ j), (1ll << Lim - now)))));
        }
    }
    return f[now][f1][f2][f3] = ans;
} 
int solve() {
    memset(vis, 0, sizeof(vis));
    memset(f, 0, sizeof(f));
    Lim = 0;
    N = read(); M = read(); K = read(); mod = read(); N--; M--;
    Lim = max(Get(N), max(Get(K), Get(M)));
    Pair ans = dfs(1, 1, 1, 1);
    return add(ans.fi, -mul(K, ans.se));
}
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...

    attack
  • 2017.10.25水题大作战题解

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

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

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

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

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

    Angel_Kitty
  • 洛谷P1567 统计天数

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

    attack
  • leetcode周赛130 | 题解速递

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

    ACM算法日常
  • Android 自定义流布局。使用开源库SimpleFlowLayout

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

    zhangyunfeiVir
  • BZOJ4260: Codechef REBXOR (01Tire树)

    attack
  • 各种平衡树

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

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

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

    attack

扫码关注云+社区

领取腾讯云代金券