← 返回题目列表

Codeforces · 332/D

D. 蓝图失窃

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

叛乱分子意外掌握了在遥远星球上为银河帝国的需要而创建的绝密研究多边形的计划。叛乱分子认为这个多边形正在开发新的致命武器。该多边形由n个导弹发射井组成,通过双向地下通道连接。这些段落与进行研究的实验室相关。当然,通道的守卫很严密:i 号发射井和 j 号发射井之间的通道由 ci、j 战争机器人巡逻。

叛乱分子研究了多边形计划并注意到其不寻常的结构。事实证明,对于任何 k 元素的筒仓 S 集,都恰好有一个筒仓通过通道与 S 中的每个筒仓直接连接(我们将此筒仓称为与 S 相邻的筒仓)。考虑到这一点,起义者决定采取以下行动:

1.他们选择一组k元素的筒仓S;
2.一组侦察兵从S处空中降落到每个发射井;
3. 每个小组沿着相应的通道移动到与S相邻的发射井(当侦察兵移动时,他们会检查实验室并观察任何武器蓝图的迹象);
4. 在与S相邻的筒仓中,各小组登上船并飞走。

该行动的危险在于巡逻侦察兵所经过通道的机器人总数。行动的危险性显然只取决于选择S组的方式。叛乱分子还没有决定将侦察兵送往哪个发射井。不过,他们已经要开始为侦察队准备武器了。为此,起义者需要知道与选择集合 S 的所有可能方式相对应的操作危险的数学平均值。解决此问题以帮助起义者保护共和国的理想!

输入

第一行包含两个整数 n 和 k (2 ≤ n ≤ 2000, 1 ≤ k ≤ n - 1) — 相应的筒仓数量和侦察组数量。接下来的 n - 1 行描述多边形计划:其中第 i 行包含 n - i 个整数 ci, i + 1, ci, i + 2, ..., ci, n — 巡逻相应通道的机器人数量(-1 ≤ ci, j ≤ 109;如果 ci, j = -1,则筒仓 i 和 j 之间没有通道)。所有通道都是双向的,也就是说,我们可以假设 ci, j = cj, i。没有通道将筒仓与其自身连接起来。保证多边形计划满足问题陈述的条件。

输出

打印侦察行动的平均危险度,向下舍入为整数。请注意,在给定的限制下,问题的答案始终符合标准整数 64 位数据类型。

请不要使用 %lld 说明符在 С++ 中写入 64 位整数。最好使用 cout 流或 %I64d 说明符。

示例

输入 #1

6 1
-1 -1 -1 8 -1
-1 5 -1 -1
-1 -1 3
-1 -1
-1

输出 #1

5

输入 #2

3 2
10 0
11

输出 #2

14

注意

在第一个示例中,有 6 个单元素筒仓集。对于集合 {1}、{5},操作危险将等于 8,对于集合 {3}、{6} — 3,对于集合 {2}、{4} — 5。数学平均值等于 $$\frac{8+8+3+3+5+5}{6}=\frac{16}{3}$$。

在第二个示例中,有 3 个双元素孤岛集:{1, 3}(危险等于 21)、{1, 2}(危险等于 11)、{2, 3}(危险等于 10)。平均操作危险等于 $${ \frac { 2 1 + 1 1 + 1 0 } { 3 } } = { \frac { 4 2 } { 3 } } = 1 4$$。