鏈接：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;
}

　　

總結

以上是生活随笔為你收集整理的和与或(数位DP + 状压)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。