此题好是怪异

玩世不恭地随便写了写就A了......rp爆发啊......

懒得打矩阵快速幂了，所以......

2-SAT太特么难了......
玛德纸张

和最小生成树并没有关系...

一言不合矩阵快速幂

%%%

还有第五种写法: DFS+剪枝
弱剪枝:前缀和计算从 ∑v[j] (i<=j<=n)
强剪枝:先按性价比排序,然后计算该条分枝的上界.

坑爹数据, 题目说是每行n个字符但是数据不按常理出牌, 直接天真傻乎乎的写:

for(int i=1;i<=n;i++)

{

 for(int j=1;j<=n;j++)

 scanf("%c",&c);

 getchar();//*

}

打星号的位置必须要写

for(c=getchar();c!='\n';c=getchar());

才行, 因为有可能n=9结果每行给10个.

把概率加起来求最大有60分...

首先把 A / B 约分成既约分数。设 a[1] = A，r[n] 为原分数小数点后第 n 位的数。
显然有 r[1] = floor(K * a[1] / B)。
剩下来的余数 a[2] = K * a[1] mod B。
依此类推我们有 r[n] = floor(K * a[n] / B)，a[n] = K * a[n - 1] mod B。
不难发现如果 a[p] = a[q]（p < q），那么小数点后第 p 位到第 q - 1 位这一段就可以视为一个循环节。
暴力计算数列 a，找到第一个与前面重复的项，就可以找到最短循环节了。
这个重复的项前面的部分导出混循环部分
如果最早在 p 处计算到 a[p] = 0，那么原分数就是一个小数点后有 p - 1 位的有限小数。
以上便是 50 分的解法。
下面我们对 a 数列的性质做一些讨论。
如果 (B, K) = 1，对于任意的 i 都有 (a[i], B) = 1。
设 K' 为 K 模 B 时的乘法逆元，即 KK' mod B = 1。由乘法逆元的性质 K' 存在且唯一。
假设最早出现重复的位置是 a[p] = a[q] (p < q)。
如果 p != 1，那么 a[p - 1] = K' * a[p] mod B = K' * a[q] mod B = a[q - 1]。
也就是出现了更早的重复，与题设矛盾。所以显然有 p = 1。
这时，显然原分数是一个纯循环小数，且最短循环节长度是 q - 1。
设 x = q - 1。显然 a[q] = a[1] * K^x mod B = a[1]，于是 K^x mod B = 1。
这就转化成了求 K 模 B 的阶的问题了。
由欧拉定理 K^phi(B) = 1 (mod B)，由阶的性质 x | phi(B)。
我们可以将 phi(B) 分解素因数，并初始化 x = phi(B)。
之后考虑 phi(B) 的每个素因数 p。如果 K^(x/p) = 1 (mod B)，就 x ← x / p，并继续试除 p。否则转下一个素因数。这样就可以求出 K 模 B 的阶了，这就是最短循环节的长度
如果 (B, K) > 1，那么 (a[2], B) > 1。设 (a[2], B) = g，不难发现对于任意的 i ≥ 2，有 g | (a[i], B)。
不妨设 B' = B / g，a'[i] = a[i] / g (i ≥ 2)。
若此时 (B', K) = 1，就转化为了上面的情况。否则继续这个过程。
如果上面的转换进行了 T 次，由于 a[1] 到 a[T] 与后面 a 数列的循环无关。
卡一下范围便会知道循环节的最后一个数字与混循环部分最后一个数字一定不相等。
于是原分数的混循环长度就是 T 了。
特殊地，如果在 T 次转换之后得到的最后一个 B = 1，那么之后 a 数列的值全为 0。这时我们可以断言原分数是一个小数点后有 T 位的有限小数。
以上便是 100 分的做法。
搬自CODE[VS]P2487
PS：这年头1星题都这么难了，这让蒟蒻怎么活

人傻自带大常数

唉明明知道是树剖然而就是不会写
= =暴露鶸渣本性

这和单调队列半毛钱关系都没有,,,就是一个裸LDS

不理解……

插排大法好

一点也不烦。。。

回复 @Tabing :
啊啊啊

一直以为自己的代码是错的，结果交进去就对了……