题意：

给你一个数组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
  2. 多个数该二进制位的都没有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的二进制下表示每个数卡不卡上界

代码：

之后更新代码
先贴上官方代码

#include <bits/stdc+