第 2 题 传糖果 (beads)

时间限制 1.0 s · 空间限制 256 MB · 145 个测试点 · 全文比较（过滤行末空格及文末回车）

本题使用文件输入输出：输入文件 beads.in，输出文件 beads.out。

KOI 2020 — 第 2 次选拔 (2차 선발) 第 2 试

题目描述

有 $N$ 个圆柱形的无盖罐子围成一圈。按顺时针方向，罐子从 1 到 $N$ 编号，每个罐子里都放着 $K$ 颗糖果，因此一共有 $N \times K$ 颗糖果。

每颗糖果的颜色用 1 到 $N$ 之间的一个正整数表示。对于每种颜色 $c$（$1 \le c \le N$），这 $N \times K$ 颗糖果中恰有 $K$ 颗颜色为 $c$。每个罐子里各糖果的颜色由输入给出。

传糖果操作按下面的顺序执行 $N$ 个动作，每次移动一颗糖果：

• 从 1 号罐中任意取出一颗糖果放进 2 号罐；
• 从 2 号罐中任意取出一颗糖果放进 3 号罐；
• ……
• 从 $(N - 1)$ 号罐中任意取出一颗糖果放进 $N$ 号罐；
• 从 $N$ 号罐中任意取出一颗糖果放进 1 号罐。

你会在初始状态下恰好执行 $Q$ 次传糖果操作。执行完之后，你希望颜色为 $c$ 的所有糖果都位于 $c$ 号罐中：即 1 号罐里只有颜色 1 的糖果，2 号罐里只有颜色 2 的糖果，……，$N$ 号罐里只有颜色 $N$ 的糖果。这样的状态称为正确状态。

给定各罐中糖果的初始情况，判断在初始状态下恰好执行 $Q$ 次传糖果操作后能否达到正确状态。

输入格式

第一行给出三个整数 $N, K, Q$，中间用一个空格隔开。

接下来 $N$ 行，第 $i$（$1 \le i \le N$）行给出 $K$ 个 1 到 $N$ 之间的整数，中间用空格隔开，表示初始状态下 $i$ 号罐中 $K$ 颗糖果的颜色。

输出格式

如果能在初始状态下恰好执行 $Q$ 次传糖果操作达到正确状态，输出 1；否则输出 0。

数据范围

• $2 \le N \le 2000$
• $1 \le K \le 2000$
• $1 \le Q \le 1\,000\,000\,000$
• 对每种颜色 $c$（$1 \le c \le N$），颜色为 $c$ 的糖果恰有 $K$ 颗。

子任务

1. (3 分) $Q = 1$。
2. (6 分) $N = 2$。
3. (28 分) $K = 1$。
4. (40 分) $N, K \le 100$。
5. (23 分) 无额外限制。

样例

样例 1

输入：

3 1 1
2
3
1

输出：

1

样例 2

输入：

2 5 2
1 1 2 2 2
2 2 1 1 1

输出：

0