#P16073. [2022国家队训练南京站]自动机

    ID: 15284 传统题 2000ms 1024MiB 尝试: 3 已通过: 1 难度: 9 上传者: 标签>CF2600省选/NOI-图构造最小公倍数不变量分析

[2022国家队训练南京站]自动机

题目描述

小 D 最近学了有限自动机上用 LCC 维护的有限群分治 DFT,并得意地到处显摆。

大 D 看不下去了,给小 D 出了一个难题。

对于字符集大小为 22 的非确定性有限自动机

G=(V,E0,E1,v0,F),G=(V,E_0,E_1,v_0,F),

定义 L(G)L(G) 为最短的不能被 GG 接受的 01 串长度;如果不存在这样的串,则 L(G)=0L(G)=0。

大 D 限制了 ∣V∣≤n|V|\le n。你需要构造一个自动机 GG,使得 L(G)L(G) 尽可能大。

自动机含义如下:

  • VV 表示点集;
  • E0,E1E_0,E_1 分别是两个定义在 VV 上的有向边集;
  • v0∈Vv_0\in V 表示起始点;
  • F⊆VF\subseteq V 表示接受点集;
  • 自动机 GG 接受长度为 kk 的 01 串 SS,当且仅当存在点序列
v0,v1,…,vkv_0,v_1,\ldots,v_k

满足 vk∈Fv_k\in F,且对所有 ii,都有

(vi−1,vi)∈ESi.(v_{i-1},v_i)\in E_{S_i}.

输入格式

一行一个整数 nn。

输出格式

输出自动机 GG。要求:

V={0,1,…,n−1},v0=0.V=\{0,1,\ldots,n-1\},\qquad v_0=0.

首先输出 E0E_0:

第一行一个整数 ∣E0∣|E_0|,满足

0≤∣E0∣≤1000.0\le |E_0|\le 1000.

接下来 ∣E0∣|E_0| 行,每行两个整数 u,vu,v,表示一条边 (u,v)(u,v)。

然后以相同格式输出 E1E_1。

最后输出接受点集 FF:

第一行一个整数 ∣F∣|F|。

接下来输出 ∣F∣|F| 个整数,表示 FF 中的点。

样例

输入

3

输出

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

解释

最短的不可被接受的字符串是 1010。

数据范围与评分

本题只有两组数据:

测试点 nn 得分
1 66 $50\max\left(0,\min\left(1,\frac{L(G)-11}{10}\right)\right)$
2 2020 $50\max\left(0,\min\left(1,\frac{\sqrt{L(G)}}{20}\right)\right)$