A*G/C011

A Airport Bus

不会zbl/kk

枚举每个开始的点直接倍增

我好像sb了，可行的是一段前缀所以可以直接2分

真tm就c都不会啊。。。

考虑图上的两条长度相等的（可以非简单）路径(a_1,ldots,a_k)和(b_1,ldots,b_k)那么点((a_i,b_i))都是连通的。

有两个连通块大小为(A,B)，要计算它们在新图中会产生多少连通块。

如果有一个是单点那么不会有边所以新图连通块数是(AB)

否则，如果有一个连通块存在鸡环，则产生1个连通块；都是二分图产生2个连通块。

如果想要一条边((a,b)-(c,d))，等价于存在一条边((a',b),(c',d))，其中(x)与(x')相邻。存在鸡环的话这条边一定可以有，因为你让一个点走到一个鸡环上打转，另一个点在一条边上反复横跳一定可以构造出方案。

是二分图的话，yyb：把二分图黑白染色之后左右分开，显然把两边的点分别放在二元组的前面都会形成一个联通块。

真打表题

打个表找出一次移动的规律是先左移再取反，然后操作(2*n)次后序列一定是ABABABABABA或BABABABA

上升数可以拆成(leq 9)个全(1)数的和，如果(0)也是全(1)数那么可以拆成正好(9)个全(1)数的和。

全(1)数可以用(frac{10^x-1}{9})表示。

假设选了(9k)个全(1)数，列出式子：

(sum_{i=1}^{9k}frac{10^{a_i}-1}{9}=n)

简单变换：

(sum_{i=1}^{9k}10^{a_i}-1=9n)

(sum_{i=1}^{9k}10^{a_i}=9(n+k))

现在假设知道(k)想求(a_i)的可行性，那么(9(n+k))的数位和就是需要非(0)的(a_i)的下界。

从小到大枚举(k)，(n)初值是(9n)，每次加上(9)（进位是均摊(O(1))的），维护一个全局数位和，当全局数位和(leq 9(n+k))就可以输出了

咕了