問題一覧 > 通常問題

No.1502 Many Simple Additions

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 40
作問者 : とりゐとりゐ / テスター : 遭難者遭難者
5 ProblemId : 6322 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-05-07 22:49:24

問題文

長さ $N$ の正整数列 $A=(A_1,A_2,\ldots,A_N)$ であって, 以下の条件を満たすものの個数を求めてください.

  • $i=1,2,\ldots,M$ について, $A_{X_i}+A_{Y_i}=Z_i$
  • $\max A=K$
ただし, 答えは非常に大きくなる場合があるので, $10^9+7$ で割った余りを答えてください.
ここで $\max A=K$ とは, すべての $i(1\leq i\leq N)$ に対して $A_i\leq K$ が成り立ち, かつ $A_j=K$ となる $j(1\leq j\leq N)$ が存在することを意味します.

入力

$N\ M\ K$
$X_1\ Y_1\ Z_1$
$\vdots$
$X_M\ Y_M\ Z_M$

  • 入力は全て整数である.
  • $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)$
  • $i\neq j$ ならば $(X_i,Y_i)\neq (X_j,Y_j)$
  • $1\leq Z_i\leq 2K(1\leq i\leq M)$

出力

条件を満たす正整数列 $A$ の数を $10^9+7$ で割った余りを求めてください.

サンプル

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

$(A_1,A_2,A_3,A_4)=(3,3,2,5),(5,1,4,3)$ が条件を満たします. $(A_1,A_2,A_3,A_4)=(4,2,3,4)$ は $\max A=5$ を満たしていないので不適です.

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

(22:48修正) $(A_1,A_2,A_3)=(2,1,3)$ が条件を満たします.

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

条件を満たす $A$ が存在しない場合もあります.

サンプル4
入力
3 1 4
1 2 6
出力
9

サンプル5
入力
4 1 100000
1 2 100000
出力
999699868

$10^9+7$ で割った余りを求めてください.

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