問題一覧 > 通常問題

No.1502 Many Simple Additions

レベル : / AI推定難易度 : 1700 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 49
作問者 : とりゐ / テスター : 👑 qand
お気に入りにしたユーザー ProblemId : 6322 / 自分の提出
問題文最終更新日: 2026-10-20 17:54:26
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 294 (順位表) の他の問題:

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$
Since the answer can be very large, output it modulo $10^9+7$.
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もしくは右上の雲マークをクリックしてアカウントを作成してください。