星際飛船 - المسألة

給定一個由 $n$ 個整數 $a_1,a_2,\ldots,a_n$ 組成的序列 $a$。

此外，給定一個包含 $q$ 次修改的集合 $S$。每次修改由三個數 $l$、$r$ 和 $x$ 定義，會將序列 $a$ 的區間 $[l,r]$ 中的每個數與 $x$ 進行 xor 運算。形式化地，對每個 $l\le i\le r$，執行下列替換：

$$a_i:=a_i\oplus x.$$

對於修改集合 $S$，將 $K(S)$ 定義為：對給定序列執行 $S$ 中的所有修改後，序列 $a$ 的所有可能區間的 $sum(i,j)^2$ 之和：

$$K(S)=\sum_{1\le i\le j\le n}sum(i,j)^2,$$

其中 $sum(i,j)$ 定義為區間 $[i,j]$ 內所有元素的總和：

$$sum(i,j)=\sum_{x=i}^{j}a_x.$$

你的任務是對給定修改集合 $S$ 的全部 $2^q$ 個子集求和。形式化地，若 $P$ 是包含 $q$ 次修改的集合 $S$ 的所有子集所構成的集合，請求出：

$$\sum_{subset\in P}K(subset).$$

第一行包含一個整數 $n$（$1\le n\le1000$），表示序列的元素個數。

第二行包含 $n$ 個以空格分隔的整數 $a_1,a_2,\ldots,a_n$（對每個 $1\le i\le n$，有 $0\le a_i<128$），表示給定的序列。

第三行包含一個整數 $q$（$1\le q\le10^5$），表示修改次數。

接下來的 $q$ 行，每行包含三個以空格分隔的整數 $l$、$r$ 和 $x$（$1\le l\le r\le n$，$0\le x<128$），描述一次修改。

輸出一個整數，表示本題的答案。由於答案可能很大，請輸出它對 $10^9+7$ 取模後的結果。

本題包含九個子任務：

$1\le n\le10$，$1\le q\le10$，對所有 $1\le i\le n$，有 $0\le a_i,x<128$。配分為 4 分。
$1\le n\le100$，$1\le q\le10$，對所有 $1\le i\le n$，有 $0\le a_i,x<128$。配分為 5 分。
$1\le n\le100$，$1\le q\le100000$，對所有 $1\le i\le n$，有 $0\le a_i,x<32$。保證所有修改區間的長度都等於 $1$。配分為 6 分。
$1\le n\le1000$，$1\le q\le500$，對所有 $1\le i\le n$，有 $0\le a_i,x<128$。保證所有修改區間兩兩不相交。配分為 9 分。
$1\le n\le30$，$1\le q\le20$，對所有 $1\le i\le n$，有 $0\le a_i,x<32$。配分為 8 分。
$1\le n\le30$，$1\le q\le5000$，對所有 $1\le i\le n$，有 $0\le a_i,x<32$。配分為 11 分。
$1\le n\le300$，$1\le q\le300$，對所有 $1\le i\le n$，有 $0\le a_i,x<128$。配分為 19 分。
$1\le n\le500$，$1\le q\le100000$，對所有 $1\le i\le n$，有 $0\le a_i,x<128$。配分為 30 分。
$1\le n\le1000$，$1\le q\le100000$，對所有 $1\le i\le n$，有 $0\le a_i,x<128$。配分為 8 分。

5
1 2 3 4 5
0

xor 運算是位元互斥或運算。

在第一個範例中，執行修改後可能得到 $2^1=2$ 個序列：執行給定的唯一一次操作，以及不執行該操作。這兩個序列得到的總和都等於 $26$。

在第二個範例中，集合 $S$ 是空集合，其所有子集構成的集合僅包含一個元素 $\varnothing$，即空集合。換言之，沒有任何修改，你必須對給定序列 $a$ 求出 $K(\varnothing)$。

QOJ.ac