这题和前几天的 每日一题 几乎是一样的，那道题下标 $i$ 处的元素能贡献 $0,1,\cdots,i$ 个逆序对，本题将连续的相同字符分块，具有 $l$ 个字符的块在初始字符串中可能有 $1,2,\cdots,l$ 个字符。

和 3193 题类似的动态规划解法可以达到 $O(k^2)$ 复杂度，3193 题的 生成函数解法 也同样适合本题。

具有 $l$ 个字符的块的生成函数为 $x+x^2+\cdots+x^l=x\dfrac{1-x^l}{1-x}$，假设总共有 $n$ 个块，生成函数即为 $\dfrac{x^n}{(1-x)^n}\prod_{i=0}^{n-1}(1-x^{l_i})$，去掉 $x^n$ 项取对数后为
$$
\sum_{i=0}^{n-1}\log(1-x^{l_i})-n\log(1-x)
$$

用泰勒展开计算 $\log$ 再取 $\exp$ 即可，和 3193 题不同的是要将长度相同的块合并处理，这样才能保证复杂度是调和级数部分和，达到 $O(k \log k)$ 的复杂度。

代码

###Python3

import numpy as np

def polymul(lhs, rhs, MOD):
    n_lhs = len(lhs)
    n_rhs = len(rhs)
    n = n_lhs + n_rhs - 1
    
    if n_lhs <= 64:
        rhs = rhs.astype(np.uint64)
        total = np.zeros(n, dtype = np.uint64)
        for i, e in enumerate(lhs):
            total[i: i + n_rhs] += np.uint64(e) * rhs % MOD
        return total % MOD
    
    elif n_rhs <= 64:
        lhs = lhs.astype(np.uint64)
        total = np.zeros(n, dtype = np.uint64)
        for i, e in enumerate(rhs):
            total[i: i + n_lhs] += np.uint64(e) * lhs % MOD
        return total % MOD
    
    else:
        p = (lhs & 65535) + 1j * (lhs >> 16)
        f_p = np.fft.fft(p, n)
        f_cp = np.conj(np.append(f_p[0:1], f_p[-1:0:-1]))

        q = (rhs & 65535) + 1j * (rhs >> 16)
        f_q = np.fft.fft(q, n)
        
        pq = np.fft.ifft(f_p * f_q, n)
        cpq = np.fft.ifft(f_cp * f_q, n)

        s = np.round(0.5 * (pq + cpq))
        d = np.round(-0.5j * (pq - cpq))

        ans00 = s.real.astype(np.uint64)
        ans01 = s.imag.astype(np.uint64)
        ans10 = d.real.astype(np.uint64)
        ans11 = d.imag.astype(np.uint64)
        
        return (ans00 % MOD + (((ans01 + ans10) % MOD) << 16) + ((ans11 % MOD) << 32)) % MOD

def polyninv(x, n, MOD):
    y = np.array([pow(MOD - int(x[0]), MOD - 2, MOD)], dtype = np.uint64)
    l = 1
    while l < n:
        l = min(2 * l, n)
        t = polymul(x[:l], y, MOD)[:l]
        t[0] += 2
        y = polymul(t, y, MOD)[:l]
    return y

def polyinv(x, n, MOD):
    return polyninv(MOD - x, n, MOD)

def polyder(x, MOD):
    return x[1:] * np.arange(1, len(x), dtype = np.uint64) % MOD

def polyint(x, INV, MOD):
    return np.append([np.uint64(0)], x * INV[:len(x)] % MOD)

def polylog(x, n, INV, MOD):
    return polyint(polymul(polyder(x[:n + 1], MOD), polyinv(x, n, MOD), MOD)[:n - 1], INV, MOD)

def polyexp(x, n, INV, MOD):
    y = np.array([1, 0], dtype = np.uint64)
    l = 1
    while l < n:
        l = min(2 * l, n)
        t = (MOD - polylog(y, l, INV, MOD))
        t[:len(x)] += x[:l]
        t[0] += 1
        y = polymul(t, y, MOD)[:l]
    return y

MOD = 1000000007
K = 2000
INV = [1] * (K + 1)
for i in range(2, K + 1):
    INV[i] = (MOD - MOD // i) * INV[MOD % i] % MOD
NP_INV = np.array(INV[1:], dtype = np.uint64)

class Solution:
    def possibleStringCount(self, word: str, k: int) -> int:
        log_f = [0] * k
        pre_ch = word[0]
        l = 0
        n = 1
        total = 1
        for ch in word:
            if ch == pre_ch:
                l += 1
            else:
                n += 1
                if l < k:
                    log_f[l] += 1
                total = total * l % MOD
                pre_ch = ch
                l = 1
        total = total * l % MOD
        if k <= n:
            return total
        if l < k:
            log_f[l] += 1
        for i in range(k - n - 1, 0, -1):
            if log_f[i] > 0:
                c = log_f[i]
                log_f[i] = 0
                for j in range(1, (k - n - 1) // i + 1):
                    log_f[i * j] -= c * INV[j]
        for i in range(1, k - n):
            log_f[i] = (log_f[i] + n * INV[i]) % MOD
        f = polyexp(np.array(log_f[:k - n], dtype = np.uint64), k - n, NP_INV, MOD)
        return (total - int(np.sum(f))) % MOD