1 条题解

  • 0
    @ 2026-11-15 21:10:33

    10pts

    暴力枚举所有可能的情况,进行判定。

    30pts

    可能满足要求的 kk 至多 1010 种,枚举哪些 kk 满足条件作容斥,把相同的数放在一起,答案为 m不同的数m^{不同的数},把所有可能的情况的答案加在一起即可。

    100pts

    我们考虑对于一个 kk 而言,满足要求的字符串有 mn−km^{n-k},但是答案会算重。

    因此我们考虑对于一个 k0k_0,计算 k0k_0 是所有满足要求的 kk 中最小的一个时的方案数。

    这意味着不存在 k<k0k<k_0,使得 S[1:k]=S[n−k+1:n]S[1:k]=S[n-k+1:n]。

    又由于 k=k0k=k_0 成立,因此 S[1:k0]=S[n−k0+1,k0]S[1:k_0]=S[n-k_0+1,k_0]。

    对比两个式子,可以得到 S[1:k]=S[k−k0+1:k0]S[1:k]=S[k-k_0+1:k_0]。

    即如果 k0k_0 是所有满足要求的 kk 中最少的一个,等价于 S[1:k0]S[1:k_0] 是一个不好的字符串,但在这里 2k≤k02k \leq k_0,而原问题中 2k<k02k<k_0,有细微差异。

    记 f[x]f[x] 为长度为 xx 的字符串中好的个数(2k<n2k<n),g[x]g[x] 为好的个数(2k≤n2k \leq n),那么有

    f[n]=∑2i<ng[i]×mn−2if[n]=\sum_{2i <n} g[i] \times m^{n-2i} g[n]=mn−∑2i≤ng[i]×mn−2ig[n]=m^n -\sum_{2i \leq n} g[i] \times m^{n-2i}

    上述表达式可以利用前缀和进行优化,时间复杂度为 O(n)O(n)。

    $$g[n]=m^n -(\sum_{2i \leq n} g[i] \times m^{-2i}) \times m^n$$
    • 1

    信息

    ID
    196
    时间
    1000ms
    内存
    512MiB
    难度
    5
    标签
    递交数
    1
    已通过
    1
    上传者