F - Best Representation

给小写字母字符串S

问S能最少被切割成多少个(?)，使得每个子串都不能表示成循环节（ababa好，ababab坏）

有多少个方案 能 达到最小的切割数 mod 1e9+7

|S| 5e5

2s

256mb

我的思路

如果整个字符串是好的，那么答案为1,1

否则 整个字符串 如果是坏的，那么它可以表示成 字符串t的重复拼接

那么 最小循环节 长度如果 > 1,那么删去最后一个 是否是一个方案呢？？

1
2
3

[.....][.....][.....][.....][.....][.....]
[...][...][...][...][...][...][...][...]
                                        x

注意到这个两个数差为1,所以gcd(len)=1

而它们相互间 多个不同偏移量的对应相等，将会像gcd过程一样对位相等

所以不可能

所以 最小分割一定是2

所以问题变成了，整个字符串有多少个切割让 left right 都是好的

同样的， 只要不是最小切割的倍数即可

所以感觉就过了?

还是有一点点问题

1
2
3

111222111222
xx
  yyyyyyyyyy

对于S的最小循环节 内还是有可能有更小的 循环的存在的

判断也好判断，如果要长度len的 循环节长度是cycle，那么len-cycle的循环节的长度是cycle的因数，注意前缀后缀都要算

然而 https://atcoder.jp/contests/arc060/submissions/50471607

ACx63,WAx2

subtask1_03.txt 和 subtask2_01.txt 炸了

1
2
3
4
5
6
7

abaababaab  
len(s) = 10, cycle size = 5  
brute force = 8  
left cycle, right not cycle, [0,5][6,9]  
abaaba  
2  
9

这样的话虽然 baab是好的，但是左边是坏的且超过了单个循环节的长度

F - Unhappy Hacking

https://atcoder.jp/contests/arc059/tasks/arc059_d

操作 push(0),push(1),pop(),其中pop在空时也可以操作

给定0/1串,问有多少不同n次的操作序列 能得到s, 方案数mod1e9+7

n 5000

2s

256mb

我的思路

对于 开头 需要计算 多少次可以在空时pop的操作 得到长度0

对于 中间 需要计算 多少次不可以在空时pop的操作 得到长度0

那么 用生成函数表示

$[x^t]g_0(x)$ 表示 $t$次操作长度0的第一种操作

$[x^t]f_0(x)$ 表示 $t$次操作长度0的第二种操作

那么有$ans = [x^{n}] g_0(x) (\cdot x \cdot f_0(x))^{|s|}$

$= [x^{n}] g_0(x) \cdot x^{|s|} \cdot f_0(x)^{|s|}$

$= [x^{n-|s|}] g_0(x) \cdot f_0(x)^{|s|}$

后面直接多项式快速幂就好了，1e9+7 原根太小,没法ntt