[vp]ARC060

提交记录

\(A.\)简单背包

\(B.\)发现如果\(b \leqslant \sqrt{n}\) 可以暴力。
对于\(b> \sqrt n\)的只有两位，设这两位是\(x,y\)
那么就是\(x+y=s\)且\(bx+y=n\)，即\((b-1)x=n-s\)
枚举\(n-s\)的倍数就做完了。

\(C.\)裸\(st\)表

\(D.\)
好题,分原串循环节的三种情况讨论:
1.没有循环节,输出\(1~1\)。
2.循环节为\(1\),输出\(n~1\)。
3.循环节\(\ge 2\)，显然最多分成\(2\)段，
我们枚举段点，判断左右是否都不循环即可，
这个可以前后各做一遍\(kmp\)，结论：有一个长度为\(x\)的循环节当前仅当

\(O(1)\)可以判断,时间复杂度\(O(n)\)