問題一覧 > 通常問題

No.1222 -101

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 54
作問者 : anagohirameanagohirame / テスター : satashunsatashun
7 ProblemId : 3252 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2020-08-31 02:38:52

問題文

長さ $N$ の整数列 $(A_1, A_2, \cdots ,A_N)$ であり，以下の条件を満たすものの個数を $10^9+7$ で割った余りを求めてください。

  • $-1\leq A_i\leq 1\ (1\le i\le N)$
  • $\displaystyle \prod_{i=L_j}^{R_j}A_i \left(= A_{L_j}\times\cdots\times A_{R_j} \right)= P_j\ (1\le j\le M)$

入力

$N\ M$
$L_1\ R_1\ P_1$
$L_2\ R_2\ P_2$
$\vdots$
$L_M\ R_M\ P_M$

  • 入力はすべて整数
  • $1\le N\le 2\times 10^5$
  • $0\le M\le N$
  • $1\le L_i\le R_i\le N$
  • $-1\le P_i\le 1$
  • $\color{red}{i \neq j \Leftrightarrow R_i \neq R_j}$

出力

答えを1行に出力してください。

サンプル

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

$-1\leq A_i\leq 1\ (1\leq i\leq 3)$ のほかに， $A_1\times A_2 = -1 ,\ A_2\times A_3 = 0$ の2条件があります。 これらを全て満たす数列 $(A_1, A_2, A_3)$ は $(1, -1 ,0),\ (-1, 1, 0)$ の2つです。

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

条件を満たす数列は存在しません。

サンプル3
入力
100 0
出力
886041711

積についての条件がないので，$A_1$ 〜 $A_{100}$ のいずれも $-1,\ 0,\ 1$ の3つから自由に選べます。よって条件を満たす数列は $3^{100}$ 通りです。
$10^9+7$ で割った余りを出力することに注意してください。

サンプル4
入力
10 7
1 4 -1
2 5 0
8 8 -1
1 6 0
8 10 -1
6 9 1
1 7 0
出力
32

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。