题目描述
求长度为(n)且仅包含小写英文字母且循环节长度恰为(n)的字符串的个数。
意思是求一个长度为(n)的字符串的个数，它的任意一个子串重复若干次都不能和原串相等
设(f(n))为长度为(n)的字符串个数，设(g(n))为题目所求答案的个数
显然
[f(n)=26^n,f(n)=sum_{dmid n}g(d)
]
第一个很显然
第二个意思是 任意一个长度为(d(dmid n))的串，重复(frac{n}{d})次的和，就是长度为(n)的字符串的个数
又设
[sum_{dmid n}mu(d)=[n=1]
]
([n=1])的意思为当(n=1)时，表达式值为(1)，否则为(0)
因为
[g(n)=sum_{mmid n}[frac{n}{m}=1]g(m)
]
当表达式为真时，(n=m)，(g(n)=g(m))
将(sum_{dmid n}mu(d)=[n=1])代入
[g(n)=sum_{mmid n}sum_{dmidfrac{n}{m}}mu(d)g(m)
]
因为(mmid n)，(dmidfrac{n}{m})，所以可以先枚举d
[g(n)=sum_{dmid n}mu(d)sum_{mmidfrac{n}{d}}g(m)
]
再看一开始的(f(n))
[f(n)=sum_{dmid n}g(d)
]
[g(n)=sum_{dmid n}mu(d)sum_{mmidfrac{n}{d}}g(m)
]
代入
[g(n)=sum_{dmid n}mu(d)f(frac{n}{d})
]
调换下标(d o frac{n}{d})
因为枚举(dmid n)等价于(frac{n}{d}mid n)
[g(n)=sum_{dmid n}mu(frac{n}{d})f(d)
]
因为
[f(n)=26^n(O(logn)快速幂)
]
[sum_{dmid n}枚举因数(O(sqrt n))
]
如何求(mu(n))？
已知$$x=prod_{i=1}{K}p_i{a_i}(p_iin prime),mu(x)=prod_{i=1}^{K}a_i=1$$
求证$$sum_{dmid n}mu(d)=[n=1]$$
证明:
设(f(n)=sum_{dmid n}mu(d))
显然(f(1)=mu(1)=1)
假设已经证明(f(1))到(f(n-1))，(f(1)=1)，(f(2))到(f(n-1))都为0
当存在某一个(a_i>0)时
[f(n)=sum_{dmid n}mu(d),f(frac{n}{p_i})=sum_{dmidfrac{n}{p_i}}mu(d)
]
[ecausefrac{n}{p_i}<n
]
[ herefore f(frac{n}{p_i})=sum_{dmidfrac{n}{p_i}}mu(d)=0
]
[f(frac{n}{p_i})=sum_{d imes p_imid n}mu(d)=0
]
[ecause f(n)=sum_{dmidfrac{n}{p_i}}mu(d)+sum_{d
otmidfrac{n}{p_i},dmid n}mu(d)
]
[f(n)=0+sum_{d
otmidfrac{n}{p_i},dmid n}mu(d)
]
设(sum_{d
otmidfrac{n}{p_i},dmid n}mu(d))中(d)分解质因数后有(b_i)个(p_i)
则
[egin{cases}b_ileq a_i(dmid n)\b_i>a_i-1(d
otmidfrac{n}{p_i})end{cases}
]
[ herefore b_i=a_i
]
[ecause a_i>1
]
[ herefore b_i>1
]
[mu(d)=0
]
[sum_{d
otmidfrac{n}{p_i},dmid n}mu(d)=0
]
[ herefore f(n)=0+0=0
]
当对于所有(a_i)，(a_i=1)时
[f(n)=sum_{dmid n}mu(d)
]
[f(n)=sum_{dmidfrac{n}{p_i}}mu(d)+sum_{dmidfrac{n}{p_i}}mu(d imes p_i)
]
[ecause a_i=1
]
所以(d)中不含(p_i)因式
[ hereforesum_{dmidfrac{n}{p_i}}mu(d imes p_i)=-sum_{dmidfrac{n}{p_i}}mu(d)
]
[ herefore f(n)=sum_{dmidfrac{n}{p_i}}mu(d)-sum_{dmidfrac{n}{p_i}}mu(d)=0
]
综上所述，(f(n)=[n=1])