概要
うっかり、$M \leq 300$ という制約がない状態で考えてしまったので、記しておきます。$N, M$ について線形です。
解法
$\xor$ ですので、$A_i$ を列ベクトル $A_i \in \F_2^{30}$ と見なしておきます（$\xor$ を単に $+$ と書いたりします）。$A_i$ を使うか否かに応じて $x_i \in \F_2$ を対応させることにすると、以下のような問題です。
・$\sum_{i=1}^N A_i x_i = X$ となる $(x_i)$ を数えてください。
・ただし $\sum_{l\leq i\leq r} x_i = t$ という制約 $M$ 個があります。
$M$ 個の制約を処理しましょう。$x_i$ の累積和 $y_0, y_1, y_2, \ldots, y_N$ を $y_i = \sum_{j=1}^i x_j$ により定義します。$(x_i) \in \F_2^N$ と、$\{(y_i)\in \F_2^{N+1}\mid y_0 =0\}$ は、$1$ 対 $1$ に対応します。この変数変換により、$M$ 個の制約は、$y_{l-1} + y_r = t$ と書き換えられます。
ひとつめの条件も書き換えましょう。$\sum_{i=1}^N A_ix_i = \sum_{i=1}^N A_i(y_i-y_{i-1})$ です。適切に $B_i$ を定めることにより、次の問題に帰着されました。
・$\sum_{i=0}^{N+1} B_i y_i = X$ となる $(y_i)$ を数えてください。
・ただし $y_0=0$ という制約、$y_l + y_r = t$ 制約という $M$ 個があります。
後者の条件を処理しましょう。まあ典型ですよね。
頂点集合を $V(G) = \{0,1,\ldots,N\}$ に、辺を貼ります。$(l,r)$ の間に属性 $t$ の辺を貼ります。各頂点 $v$ を $y_v\in \{0, 1\}$ の $2$ 値で塗り分けて、$t = y_l + y_r$ にしてくれという話です。
これは、連結成分ごとに、次のどちらかです。
- 条件どうしが矛盾する
- ある塗り分け方に加えて、全ての色を逆転した場合の $2$ 通りの塗り分け方がある。
とりあえず、$y_0 = 0$ のもとで、塗り分け方を $1$ つ作りましょう。矛盾したら $0$ 通りを出力してプログラムを終了します。
塗分け方を $1$ 通り手に入れたら、その時点での $X_0 = \sum B_iy_i$ を計算します。この値から、各連結成分 $C$ に対し、$S_C = \sum_{v\in C}B_v$ を加える・加えないのどちらかを選択して $X$ を作れるかという話です（ただし $y_0$ を含む連結成分についてはこの選択はできません）。
$X_0 + \sum_{c\in C}S_c z_c = X$ となる $(z_c) \in \F_2^C$ を数えればよいです。あとはただの連立 $1$ 次方程式なので、行基本変形すれば解けます（Gauss Jordan法というそうです）。
