【每日一题】1月29日题目 和与或
和与或
https://ac.nowcoder.com/acm/problem/21336
题意：
给你一个数组R，包含N个元素，求有多少满足条件的序列A使得
0 ≤ A[i] ≤ R [ i ]
A[0]+A[1]+…+A[N−1] =A[0] | ]A[1]… | A [ N − 1 ]
输出答案对1e9+9取模
题解：
参考博客
数位dp问题
如果和等于或的话，说明两种情况：
- 多个数的该二进制位只有一个1
- 多个数该二进制位的都没有1
说明要满足等式，每一位数的二进制只能出现在这个n个数中的某一位上
因为加法是把每个二进制位上的数字加起 而或是最多只能有1 如果有一个二进制位有两个数都是1 那么一定会导致这个位往上一位进1 那就影响其他位了 一定不可能相等的 101和10 = = 111 加起来也是 但110+10 = = 1000 110|10 = = 110
我们简化问题，对于(a,b),如果a + b= a | b且a<=r0&&b<=r1
设dp[len][limit1][limit2]表示枚举到二进制第len位，a是否限制，b是否限制，limit1和limit2的值为0或1,
这样我们只需要暴力考虑当前位二进制填0还是1，并考虑是填在a还是b
现在将问题扩展，对于(a,b,c,.....)，根据题目n最多10，那我们开个11维的数组就可以了dp[len][2][2]....[2]，但是我们注意到从第二位到最后一位都只用来表示0和1，那么我们将这些压缩，用二进制压缩，这样就成二维数组了dp[len][x].x的二
剩余60%内容，订阅专栏后可继续查看/也可单篇购买
牛客每日一题 文章被收录于专栏
记录牛客的每日一题
查看12道真题和解析