問題一覧 > 通常問題

No.1502 Many Simple Additions

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

問題文

長さ N の正整数列 A=(A1,A2,…,AN) であって, 以下の条件を満たすものの個数を求めてください.

  • i=1,2,…,M について, AXi+AYi=Zi
  • maxA=K
ただし, 答えは非常に大きくなる場合があるので, 109+7 で割った余りを答えてください.
ここで maxA=K とは, すべての i(1≤i≤N) に対して Ai≤K が成り立ち, かつ Aj=K となる j(1≤j≤N) が存在することを意味します.

入力

N M K
X1 Y1 Z1
⋮
XM YM ZM

  • 入力は全て整数である.
  • 2≤N≤105
  • 1≤M≤min(105,N(N−1)/2)
  • 1≤K≤109
  • 1≤Xi<Yi≤N(1≤i≤M)
  • i≠j ならば (Xi,Yi)≠(Xj,Yj)
  • 1≤Zi≤2K(1≤i≤M)

出力

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

サンプル

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

(A1,A2,A3,A4)=(3,3,2,5),(5,1,4,3) が条件を満たします. (A1,A2,A3,A4)=(4,2,3,4) は maxA=5 を満たしていないので不適です.

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

(22:48修正) (A1,A2,A3)=(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

109+7 で割った余りを求めてください.

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