題意 ：

• 原序列長為n，給m個連續子序列的左右端點的下標以及該連續子序列的或和，保證這m個連續子序列的并集包含原序列每一個點，求原序列的所有子序列的異或的和，輸出任意一種

思路 ：

• 由于位運算對每個位都是獨立的，考慮分別對每一位求解
• 首先看輸入的給我們帶來什么，對于[l,r]得到的同或和x，考慮它的某一位，如果這一位是0，說明[l,r]每個元素這位都是0，如果這一位是1，至少有1個1，后者沒什么用
• 考慮某一位bit，一共有n個元素，假設有a個1，b個0，顯然有$a+b=n$
• 我們如果要對結果（所有子序列異或和的總和），就要選出若干個元素使它們異或和為1，根據異或和的性質，需要選擇奇數個1和若干個（0）0
• 選奇數個1的方案為$C_a^1+C_a^3+...=2^{a?1}$，選任意個0的方案為$2^b$
• 根據乘法原理，總方案數為$2^{a?1}?2^b=2^{a+b?1}=2^{n?1}$，在當前bit位上貢獻為$1<<bit$
• 所以對于每個位，只要有1，那么這個位對結果的貢獻就是$2^{n?1}?(1<<bit)$，否則這個位對結果的貢獻是0
• 假設bit位存在1，那么v中就可以拆除一塊(1 << bit)，我們按照這種方法把v拆成若干個塊，每個塊都能產生這么多貢獻，因此可以直接用v乘上$2^{n?1}$得到答案
• 即，只要看哪些位有1，$(1<<bit)?2^{n?1}$即可，事實上，設置一個初始變量v為00…0，每次讀入一個區間，都能知道哪些位現在至少有一個1，這個位可以被累加答案了，v|=x

#include <iostream> #include <algorithm> #include <cstring> #include <vector> #include <unordered_set> #include <math.h> #define endl '\n' #define fi first #define se second #define pb push_backusing namespace std; using ll = long long;typedef pair<int, int> PII;const ll mod = 1e9 + 7;void solve() {int n, m, v = 0; cin >> n >> m;for (int i = 1, l, r, x; i <= m && cin >> l >> r >> x; i ++ ) v |= x;ll fac = 1;for (int i = 1; i <= n - 1; i ++ ) fac = fac * 2ll % mod;cout << fac * v % mod << endl; }int main() {cin.tie(nullptr) -> sync_with_stdio(false);int _;cin >> _;while (_ -- )solve();return 0; }

總結

以上是生活随笔為你收集整理的Divan and bitwise operations 异或，同或，组合数学（1500）的全部內容，希望文章能夠幫你解決所遇到的問題。

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