Flight Routes

题目描述

Bessie 最近发现她最喜欢的流行歌手 Elsie Swift 将在她全新的 Eras Tour 中演出！不幸的是，门票很快售罄，所以 Bessie 正考虑飞到另一个城市去看演唱会。

Eras Tour 将在 $N$（$2\le N\le 750$）个城市举行，城市编号为 $1\dots N$。对于每一对城市 $(i,j)$ 且 $i<j$，要么存在一条从 $i$ 到 $j$ 的直达航班，要么不存在。

从城市 $a$ 到城市 $b$（$a<b$）的一条航线（flight route）定义为一个长度为 $k\ge 2$ 的城市序列 $a=c_1<c_2<\dots<c_k=b$，使得对每个 $1\le i<k$，都存在从城市 $c_i$ 到城市 $c_{i+1}$ 的直达航班。对于每一对城市 $(i,j)$ 且 $i<j$，你会得到它们之间航线条数的奇偶性（偶数为 0，奇数为 1）。

Bessie 在规划行程时分心了，现在想知道有多少对城市之间存在直达航班。可以证明答案是唯一确定的。

输入格式

第一行包含 $N$。

接下来有 $N-1$ 行。第 $i$ 行包含 $N-i$ 个整数。第 $i$ 行的第 $j$ 个整数等于从 $i$ 到 $i+j$ 的航线条数的奇偶性。

输出格式

输出存在直达航班的城市对数量。

3
11
1

2

5
1111
101
01
1

6

提示

有两条直达航班：$1\to 2$ 和 $2\to 3$。从 $1$ 到 $2$ 以及从 $2$ 到 $3$ 各有一条航线，且都由一条直达航班构成。从 $1$ 到 $3$ 有一条航线（$1\to 2\to 3$）。

有六条直达航班 $1\to 2, 1\to 4, 1\to 5, 2\to 3, 3\to 5, 4\to 5$。 这些会产生如下航线条数： Flight Route Counts:

        dest
      1 2 3 4 5

   1  0 1 1 1 3 
   2  0 0 1 0 1 

source 3 0 0 0 0 1 4 0 0 0 0 1 5 0 0 0 0 0 对所有数取 $\pmod{2}$ 后，就与样例输入等价。

SCORING: Inputs 3-4: $N\le 6$ Inputs 5-12: $N\le 100$ Inputs 13-22: No additional constraints. Problem credits: Benjamin Qi

标签: USACO|2023|Gold

来源

USACO|2023|Gold