No.803 Very Limited Xor Subset

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 36
作問者 : tempura_pptempura_pp / テスター : heno_codeheno_code
8 ProblemId : 2818 / 出題時の順位表

問題文

henoくんは長さ$N$の整数列$A_1,\ A_2,\cdots ,\ A_N$と整数$X$を持っています。 henoくんは以下の問題を考えていました。

「$A_1,\ A_2,\cdots ,A_N$の中から0個以上を選んで、選んだすべての整数のビットごとの排他的論理和を計算する。 計算結果が$X$となるような整数の選び方は何通りあるか?」

henoくんは排他的論理和が大好きなのでこの問題は少し簡単すぎました。そこでさらに以下の形式のいずれかで表される 条件を$M$個加えることにしました。

  • $0\ l\ r\ $: $A_l,\ A_{l+1},\cdots ,\ A_r$の中から選ぶ個数は偶数個(0個でもよい)。
  • $1\ l\ r\ $: $A_l,\ A_{l+1},\cdots ,\ A_r$の中から選ぶ個数は奇数個。
$M$個の条件がすべてみたされるように0個以上の整数を選び、それらの排他的論理和を$X$にする方法が何通りあるかを、 $10^9+7$で割った余りを求めてください。ただし、0個選んだときの排他的論理和は0であるとします。

入力

$N\ M\ X$
$A_1 A_2 \cdots A_N$
$type_1\ l_1\ r_1$
$type_2\ l_2\ r_2$
$\vdots$
$type_M\ l_M\ r_M$

  • $1\le N \le 300$
  • $0\le M \le min(300,\frac{N(N+1)}{2})$
  • $0\le X,\ A_i \le 10^9$
  • $type_i\ =\ 0,\ 1$
  • $1 \le l_i \le r_i\le N$
  • $i \neq j$ならば$(l_i,\ r_i)\neq (l_j,\ r_j)$
  • 与えられる入力はすべて整数

出力

条件をみたす整数の選び方の個数を$10^9+7$で割った余りを1行に出力してください。

サンプル

サンプル1
入力
4 2 3
1 1 2 2
0 2 3
0 1 4
出力
2

すべての条件をみたす選び方は$\{a_1,\ a_4\},\ \{a_2,\ a_3\}$ の2通りです。

サンプル2
入力
4 1 3
1 1 2 2
1 1 4
出力
0

全体から奇数個を選んでなおかつ排他的論理和を3にすることはできません。

サンプル3
入力
7 3 2
1 2 3 4 5 6 7
0 2 4
0 5 6
1 2 6
出力
0

サンプル4
入力
15 5 12582921
12582923 10485775 5242888 9437185 3145743 10485768 13631489 2097158 11534339 15 14680065 6291461 7340039 10485764 7340035
1 4 11
0 5 6
0 13 15
0 1 10
0 8 11
出力
8

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。