← 返回题目列表

AtCoder · typical90_ci

087. 鸟大的要求(★5)

中文机器翻译题面 查看原题

配点: 5 点

問題文

AtCoder国家有 有 N 个城镇,每个城镇都有 它的编号为 1, 2, \cdots, N 。任何 2 两个城镇之间有公路,只需支付交通费(单位:斯努克)即可从一个城镇前往另一个城镇。

AtCoder 国务部长必须首先 确定正整数 X 后,每个 我们决定将团体 (i, j) (i \neq j) 的交通费用设置如下。

  • A_{i,j} \neq -1 时间:城市 连接 i 和城市 j 的道路的运输成本为 A_{i,j} 斯努克
  • A_{i,j} =-1 时间:城市 连接 i 和城市 j 的道路的运输成本为 X 斯努克

此外,根据Chokdai国王的意愿,必须满足以下要求。

通过选择正确的路线,您可以 总计高达 i 从城市出发 j 总计达 P 小于或等于 Snook 可达的集合。 (i, j) [1 \leq i < j \leq N] 只是 K 存在。

能够满足Chokdai国王愿望的东西。 有多少种选择 X 的方法?但如果数量无限,请报告。

制約

  • 2 \leq N \leq 40
  • 1 \leq P \leq 10^9
  • 0 \leq K \leq \frac{N(N-1)}{2}
  • i \neq j 如果 可以认为 1 \leq A_{i,j} \leq 10^8 这个类型的变量里只能放入 A_{i,j}=-1
  • i=j 如果 可以认为 A_{i,j}=0
  • A_{i,j}=A_{j,i}
  • 所有输入均为整数

入力

输入是按以下格式从标准输入给出的。 逐行打印

N P K
A_{1,1} \cdots A_{1,N}
\vdots
A_{N,1} \cdots A_{N,N}

出力

满足Chokdai国王愿望的正整数。 如果 X 的数量是有限的,那么该数量是无限的。 Infinity 。


入力例 1

3 4 2
0 3 -1
3 0 5
-1 5 0

出力例 1

3

例如,X=3 ,则如下 4 斯努克下方可到达的城镇对数量正好是 2 因此,它满足了Chokdai国王的愿望。

  • 街 1 来自城市 至 2 哈哈 4 可到达斯努克下方
  • 街 1 来自城市 至 3 哈哈 4 可到达斯努克下方
  • 街 2 来自城市 至 3 哈哈 4 斯努克下方无法到达

另外, 无需打印X = 2, 3, 4 满足 Chokdai 国王的意愿,而其他时候则不满足,所以答案是 所有 3 。


入力例 2

3 10 2
0 -1 10
-1 0 1
10 1 0

出力例 2

Infinity

X \geq 11 的正整数 X 将实现Chokdai国王的遗愿。因此,有无数个 它应该打印 Infinity 。


入力例 3

13 777 77
0 425 886 764 736 -1 692 660 -1 316 424 490 423
425 0 -1 473 -1 311 -1 -1 903 941 386 521 486
886 -1 0 605 519 473 775 467 677 769 690 483 501
764 473 605 0 424 454 474 408 421 530 756 568 685
736 -1 519 424 0 -1 804 598 911 731 837 459 610
-1 311 473 454 -1 0 479 613 880 -1 393 875 334
692 -1 775 474 804 479 0 579 -1 -1 575 985 603
660 -1 467 408 598 613 579 0 456 378 887 -1 372
-1 903 677 421 911 880 -1 456 0 859 701 476 370
316 941 769 530 731 -1 -1 378 859 0 800 870 740
424 386 690 756 837 393 575 887 701 800 0 -1 304
490 521 483 568 459 875 985 -1 476 870 -1 0 716
423 486 501 685 610 334 603 372 370 740 304 716 0

出力例 3

42