题目描述

给你一个长度为的序列，问你最多可以构造多少个长度为的非负数序列，使得中每个位置都对应的相应位置并且小于等于它。并且序列还要满足。

。 。

Solution

首先看式子，涉及位运算转换二进制位看一下，通过草稿纸上推算一下我们就能得到，这个式子满足的条件是中元素相加不能产生二进制进位。也就是二进制表示中每一个的位置必须只能属于一个。那么问题就转换成了给定每个元素的上界，问你存在几种方案数使得每一个二进制只能出现一次。有上界求方案数，解决方案就是数位了。

并且我们看，这个题目和一般的数位不同的地方是，一般的数位是固定了每个位置的上下界，只需要在往下探的过程中处理不要溢出当前位置的上界和下界即可，但是这个题目是，如果一个数给出的是这个元素，如果它的最高位选择是也就是第位我们选择是，那么它后续还会存在限制，第位和第位一定只能选取，无法选取。但是如果我们最高位选取，那么它后续选择就不存在限制，第位第位也可以选择为，也就是它脱离了它的上界了。这也是比较特殊的点，这题的上下界是对于特定元素而言的，所以我们需要一个快速统计当前状态下那些数不处于上界了。这就是我们后续数位的状压元。
我们从高到底枚举每一个二进制位记为。并且计算当前这个二进制位那些元素可能满足这一位是的。这里可以使用状压处理快速统计以及后面的查询。那么如果这一位我们选择放，说明上述状压得到的全部这一位是的元素位置，都将不处于上界。如果这一位放，首先这个实现需要枚举全部的数，首先看下第个数如果它不处于上界那么这个位置就让第个元素填充，并且其他这一位本应该为的数全部脱离上界。还有如果一个数还处于上界，并且它的这一位二进制是，那么我们就吧它设定为当前位置的贡献来源，它仍要保持上界，其他元素就可以脱离了。

很不错的数位题目。还要注意的是..

#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(__vv__) (__vv__).begin(), (__vv__).end()
#define endl "\n"
#define pai pair<int, int>
#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
#define rep(i, sta, en) for(int i=sta; i<=en; ++i)
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op)    putchar(op); return; }    char F[40]; ll tmp = x > 0 ? x : -x;    if (x < 0)putchar('-');    int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';        tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]);    if (op)    putchar(op); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;    while (b) { if (b & 1)    ans *= a;        b >>= 1;        a *= a; }    return ans; }    ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int MOD = 1e9 + 9;
const int INF = 0x3f3f3f3f;
const int N = 10 + 7;

ll n, m;
ll a[N], dp[64][1 << 12];

int dfs(int len, int limit) { // limit的二进制第i位是0表示a[i]仍处于上界
    if (len == -1)    return 1;
    if (~dp[len][limit])    return dp[len][limit];
    int res = 0;
    rep(i, 1, n) {
        if (a[i] & (1ll << len))
            res |= (1 << i);
    }
    ll ans = dfs(len - 1, res | limit); // 第len个二进制位取0
    rep(i, 1, n) {
        if ((1 << i) & limit)
            //如果第i个数第len个二进制位之前有某个地方是0说明它不存在限制；
            //并且它这个位置选为1后，其他这个二进制位置也是1的也可以不存在限制了
            ans = (ans + dfs(len - 1, res | limit)) % MOD;
        else if (res & (1 << i))
            ans = (ans + dfs(len - 1, (res ^ (1 << i)) | limit)) % MOD;
    }
    return dp[len][limit] = ans;
}

void solve() {
    ms(dp, -1);
    n = read();
    rep(i, 1, n)    a[i] = read();
    ll ans = dfs(62, 0);
    print(ans);
}

int main() {
    //int T = read();    while (T--)
    solve();
    return 0;
}