No.1222 -101
タグ : / 解いたユーザー数 56
作問者 :
anagohirame
/ テスター :
satashun
Problem Statement
Find the number, modulo $10^9+7$, of integer sequences $(A_1, A_2, \cdots ,A_N)$ of length $N$ that satisfy the following conditions.
- $-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)$
Input
$N\ M$ $L_1\ R_1\ P_1$ $L_2\ R_2\ P_2$ $\vdots$ $L_M\ R_M\ P_M$
- All input values are integers.
- $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}$
Output
Output the answer on one line.
Sample
Sample 1
Input
3 2 1 2 -1 2 3 0
Output
2
In addition to $-1\leq A_i\leq 1\ (1\leq i\leq 3)$, there are two conditions: $A_1\times A_2 = -1 ,\ A_2\times A_3 = 0$. There are two sequences $(A_1, A_2, A_3)$ satisfying all of these: $(1, -1 ,0),\ (-1, 1, 0)$.
Sample 2
Input
4 3 1 2 1 2 3 0 3 4 -1
Output
0
No sequence satisfies the conditions.
Sample 3
Input
100 0
Output
886041711
Since there are no conditions on products, each of $A_1$ to $A_{100}$ can be freely chosen from the three values $-1,\ 0,\ 1$. Thus, there are $3^{100}$ sequences satisfying the conditions.
Note that you must output the count modulo $10^9+7$.
Sample 4
Input
10 7 1 4 -1 2 5 0 8 8 -1 1 6 0 8 10 -1 6 9 1 1 7 0
Output
32
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。