链接：https://ac.nowcoder.com/acm/problem/21336
来源：牛客网
题目描述
给你一个数组R，包含N个元素，求有多少满足条件的序列A使得
0 ≤ A[i] ≤ R[i]
A[0]+A[1]+…+A[N-1]=A[0] or A[1]… or A[N-1]
输出答案对1e9+9取模
输入描述:
第一行输入一个整数N (2 ≤ N ≤ 10)
第二行输入N个整数 R[i] (1 ≤ R[i] ≤ 1e18)
输出描述:
输出一个整数
示例1
输入
2 3 5
输出
15
示例2
输入
3 3 3 3
输出
16
示例3
输入
2 1 128
输出
194
示例4
输入
4 26 74 25 30
输出
8409
示例5
输入
2 1000000000 1000000000
输出
420352509
备注:
子任务1: n <= 3
子任务2: n <= 5
子任务3: 无限制
析：一个数位DP，首先可以根据题目分析出来对于每个数字A[i]的第 j 个二进制位数字最多是只有一个，只有这样，才能得到按位或和求和的值一样，因为如果第 j 个二进制位大于一个1，那么求和就必然是大于按位或的值，因为按位或最多只能使用一个数字1，而和可以同时使用所有的1。比如有两个数二进制数字形式，111 001，那么最后一位有两个1，按位或的结果就是 111，而求和的结果就是1000,必然是大于111的，如果两个数字是 110 和 001，这样每个二进制位只有一个1，那么按位或结果就是111，同时求和结果也是111，就是一样的，如果都是0，也就无所谓了。这个结论还是很容易的得到的，然后定义状态dp[i][j]表示前 i 位（二进制），这 n 个有限制状态为 j 的个数。比如dp[2][5]表示前 2 位，第1个数和第3个数限制的个数（5 = 101），因为如果有限制，对于下一位的取值有影响，这都是很简单的数位DP的道理，不多说了。这样就很容易进行数位DP转移了。
代码如下：
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <cstdio>
#include <string>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <cstring>
#include <set>
#include <queue>
#include <algorithm>
#include <vector>
#include <map>
#include <cctype>
#include <cmath>
#include <stack>
#include <sstream>
#include <list>
#include <assert.h>
#include <bitset>
#include <numeric>
#define debug() puts("++++")
#define gcd(a, b) __gcd(a, b)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define fi first
#define se second
#define pb push_back
#define sqr(x) ((x)*(x))
#define ms(a,b) memset(a, b, sizeof a)
#define sz size()
#define be begin()
#define ed end()
#define pu push_up
#define pd push_down
#define cl clear()
#define lowbit(x) -x&x
#define all 1,n,1
#define FOR(i,n,x) for(int i = (x); i < (n); ++i)
#define freopenr freopen("in.in", "r", stdin)
#define freopenw freopen("out.out", "w", stdout)
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> P;
const int INF = 0x3f3f3f3f;
const LL LNF = 1e17;
const double inf = 1e20;
const double PI = acos(-1.0);
const double eps = 1e-8;
const int maxn = 10 + 7;
const int maxm = 2000000 + 7;
const LL mod = 1e9 + 9;
const int dr[] = {-1, 1, 0, 0, 1, 1, -1, -1};
const int dc[] = {0, 0, 1, -1, 1, -1, 1, -1};
int n, m;
inline bool is_in(int r, int c) {
return r >= 0 && r < n && c >= 0 && c < m;
}
LL dp[70][1024];
LL a[maxn];
LL dfs(int pos, int ok){
if(pos == -1) return 1;
LL &ans = dp[pos][ok];
if(ans >= 0) return ans;
int is = 0;
for(int i = 0; i < n; ++i)
if(ok&1<<i && !(a[i]&1LL<<pos)) is ^= 1<<i;
LL res = dfs(pos-1, is);
for(int i = 0; i < n; ++i){
if(!(ok&1<<i) || a[i]&1LL<<pos) res += dfs(pos-1, ok&1<<i&&a[i]&1LL<<pos?is^1<<i:is);
}
res %= mod;
return ans = res;
}
int main(){
cin >> n;
for(int i = 0; i < n; ++i) cin >> a[i];
ms(dp, -1);
cout << dfs(60, (1<<n)-1) << endl;
return 0;
}
