No.1502 Many Simple Additions
Problem Statement
Find the number of sequences of positive integers $A=(A_1,A_2,\ldots,A_N)$ of length $N$ that satisfy the following conditions.
- For $i=1,2,\ldots,M$, $A_{X_i}+A_{Y_i}=Z_i$
- $\max A=K$
Here, $\max A=K$ means that $A_i\leq K$ holds for all $i(1\leq i\leq N)$ and there exists $j(1\leq j\leq N)$ such that $A_j=K$.
Input
$N\ M\ K$ $X_1\ Y_1\ Z_1$ $\vdots$ $X_M\ Y_M\ Z_M$
- All inputs are integers.
- $2\leq N\leq10^5$
- $1\leq M\leq \min(10^5,N(N-1)/2)$
- $1\leq K\leq 10^9$
- $1\leq X_i\lt Y_i\leq N(1\leq i\leq M)$
- $1\leq Z_i\leq 2K(1\leq i\leq M)$
Output
Output the number of sequences of positive integers $A$ satisfying the conditions, modulo $10^9+7$.
Sample
Sample 1
Input
4 3 5 1 2 6 2 3 5 3 4 7
Output
2
$(A_1,A_2,A_3,A_4)=(3,3,2,5),(5,1,4,3)$ satisfy the conditions. $(A_1,A_2,A_3,A_4)=(4,2,3,4)$ does not satisfy $\max A=5$, so it is invalid.
Sample 2
Input
3 3 3 1 2 3 1 3 5 2 3 4
Output
1
(Corrected at 22:48) $(A_1,A_2,A_3)=(2,1,3)$ satisfies the conditions.
Sample 3
Input
2 1 3 1 2 2
Output
0
There may be no $A$ satisfying the conditions.
Sample 4
Input
3 1 4 1 2 6
Output
9
Sample 5
Input
4 1 100000 1 2 100000
Output
999699868
Output the remainder when divided by $10^9+7$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
とりゐ