题目描述
给你一个数组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<=10 ； A[i]<=1E18

记忆化搜索好题

分析 ：题目要求 A1+A2+A3…+AN=A1|A2|A3…|AN ，把｜运算符用+号来表示，A1|A2=A1+A2-2*(A1&A2),可以推出，把A1-AN转化成二进制表达后，同一位二进制位上不能有两个以上的1，不然一定会出现式子里的减法从而小于A1+A2…+AN，我们不妨设SUM为所有A数组的和，然后把SUM转化成二进制，条件就被我们转化成，SUM二进制上的 1 只会来源于N个Ai中的一个，根据这个设计DP的状态表示。

状态表示：DP[iI[j]（i=62，j=1<<12）表示枚举到sum二进制的第i位时，R数组里各个数字的限制情况，这里特别解释下限制的意思，因为我们枚举SUM二进制时要考虑二进制上1的来源，设R1=10010（二进制），如果SUM的第五位是由A1的数字贡献的，既A1>=10000,那么当我们继续考虑第四位的1时，A1必然无法继续作出贡献，会导致A1超出R1的限制，直到枚举至第二位，它本身上界有1时，才能继续贡献，可是如果之前第5位的时候A1不贡献1,那么根据二进制，高位的1大于所有比它低位的1的和（10000>01111），既A1<10000，那么在考虑后面4，3，2，1位的时候，A1可以任意选择贡献1还是不贡献1，这就是限制与不限制的区别。至此J的含义已经清楚 J可以被当成一个12位的二进制数，如果第一位上是1则代表，A1是不受限制的，反之则受限，受限的Ai只能在其上届Ri有1的时候才能作出贡献。

转移方程：假设枚举到第I位，限制状态是J，如果SUM该位二进制数取0，则在该位上是1的R[i],在之后的搜索中全部变成无限制，而如果取1，1的来源有两种情况，一种是R[I]被限制了，但这一位上有1，那么R[I]依旧保持限制，其他这一位上有1的变为无限制，第二种是R[I]没被限制，那么R[I]保持无限制，其他这一位上有1的也为无限制。当然之前就已经无限制的数字在之后依旧无限制，总计三种情况，记忆化搜索。
//喜欢的话可以帮忙去CSDN加个点击）https://blog.csdn.net/NODOGNOFAIL/article/details/109720902
初始所有的数字都是被限制的。

#include <stdio.h>
#include <cstring>
#include<stack>
#include<deque>
#include<cstdio>
#include<cmath>
#include<ctime>
#include<algorithm>
#include <iostream>
#include<bitset>
#include <queue>
#include<set>
#include <map>
#include<unordered_map>
#define For(i, R, y) for(int i=R;i<=y;i++)
#define _For(i, R, y) for(int i=R;i>=y;i--)
#define Mem(f,R) memset(f,R,sizeof(f))
#define Sca(R) scanf("%d", &R)
#define Sca2(R,y) scanf("%d%d",&R,&y)
#define Sca3(R,y,z) scanf("%d%d%d",&R,&y,&z)
#define Scl(R) scanf("%lld",&R)
#define Pri(R) printf("%d\n",4 R)
#define Prl(R) printf("%lld\n",R)
#define LL long long
#define ULL unsigned long long
using namespace std;
const int INF = 0x3f3f3f3f;
const int mod=1e9+9;

int dp[63][1<<12];
long long R[12];
int n;
int dfs(int p,int limit){
    //cout<<p<<" "<<limit<<endl;
    if(p<0) return 1;
    if(dp[p][limit]!=-1) return dp[p][limit];
    int ans=0;//用来记录第P位上有1的R[i],用于后续的限制解除.
    for(int i=1;i<=n;i++)
        if(R[i]&((long long)1<<p))
            ans|=(1<<i);
    long long res=0;
    res+=dfs(p-1,ans|limit);//如果第P位取0，所有ans记录的Ri全部解除限制ans｜limit。
    for(int i=1;i<=n;i++){
        if(((long long)1<<i)&limit)//取1的时候，如果Ri已经无限制了，保持无限制，其他这一位上有1的也为无限制。当然之前就已经无限制的数字在之后依旧无限制
            res+=dfs(p-1,ans|limit);
        else if(!((1<<i)&limit)&&ans&(1<<i))//R[I]被限制了，但这一位上有1，那么R[I]依旧保持限制，其他这一位上有1的变为无限制
            res+=dfs(p-1,(ans^(1<<i))|(limit));
    }
    dp[p][limit]=res%mod;
    return dp[p][limit];
}

int main(){
    memset(dp,-1,sizeof(dp));
    cin>>n;
    for(int i=1;i<=n;i++){
        scanf("%lld",&R[i]);
    }
    dfs(61,0);
    cout<<dp[61][0]<<endl;
    return 0;
}