和与或

题意：
有一个长度为N的数组R，求有多少满足条件的序列A使得
0 ≤ A[i] ≤ R[i]
A[0]+A[1]+...+A[N-1]=A[0] or A[1]... or A[N-1]
输出答案对1e9+9取模

思路：
由于A的N个数和与或结果相等，所以每一位最多存在于这n个数中的其中一个数中。所以可以从高位到低位枚举结果，用数位dp和状压思想优化。
dp[i][j]表示从第0位枚举到i位并且此时状态位j时满足条件的方案数。
（j在第o位为1表示第o个数在第i位取数一定小于等于该数在第i位的值，j在第o位为0表示第o个数在第i位可以随便取值，保证枚举时A[i]<=R[i]）。

代码：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const ll inf=1e9+9;

ll n, a[15], dp[65][2005];

ll dfs(ll pos,ll s)
{
    if(pos<0)
    {
        return 1LL;
    }
    if(dp[pos][s]!=-1)
    {
        return dp[pos][s];
    }
    ll ans=0, s1=s;
    for(int i=0;i<n;i++)
    {
        if(((s>>i)&1)&&(!((a[i]>>pos)&1)))
        {
            ;
        }
        else if(((s>>i)&1))
        {
            s1=s1-(1LL<<i);
        }
    }
    ans=(ans+dfs(pos-1,s1))%inf;
    for(int i=0;i<n;i++)
    {
        if((!((s>>i)&1))||(((s>>i)&1)&&((a[i]>>pos)&1)))
        {
            if(((s>>i)&1)&&(((a[i]>>pos)&1)))
            {
                ans=(ans+dfs(pos-1,s1|(1LL<<i)))%inf;
            }
            else
            {
                ans=(ans+dfs(pos-1,s1))%inf;
            }
        }
    }
    if(dp[pos][s]==-1)
    {
        dp[pos][s]=ans;
    }
    return ans;
}

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