题目描述

难度分:$1600$

输入$n$、$m$、$k(1 \leq n,m,k \leq 2000)$。

输出有多少个长为$n$的字符串$s$，满足$s$中的每个长为$k$的连续子串都是回文串。其中$m$为字母表的大小，答案模$10^9+7$。

输入样例$1$

1 1 1

输出样例$1$

1

输入样例$2$

5 2 4

输出样例$2$

2

算法

并查集+组合数学

比较容易想，分为$k$为奇数和$k$为偶数两种情况。如果是前者，那么回文串两翼之间的距离至少是$1$，随着距离中心越远，距离就会以$2$为步长递增，变为$3$、$5$、$7$……

因此对于$i$，假设它是回文串的左翼，它对应的右翼是$j$（因为$i$和$j$之间至少要有一个字符，所以$j$从$i+2$开始取），则有$[i,j]$的长度$j-i+1$为奇数。只要$i$左边和$j$的右边有足够的字符使得$[i,j]$作为中心，加上旁边相同的字符数可以构成长度为$k$的串，那么$i$和$j$位置就应该是同一个字符。

到这里就很容易想到，把肯定是同一个字符的所有位置合并成一个连通块，用并查集来解决本题。假设最后有$cnt$个连通块，每个连通块可以取$m$种字母，总的方案数就是$m^{cnt}$，用快速幂求一下返回就可以了。同理可以分析$k$为偶数的情况，只不过$j-i+1$是偶数，$j$从$i+1$开始取。

复杂度分析

时间复杂度

遍历$i$，对每个$i$枚举$j$，时间复杂度是$O(n)$。而对于可以配对的$(i,j)$，需要进行并查集合并操作，时间复杂度大概是$O(logn)$级别。而后面组合数的计算就是个快速幂，在最差情况下$cnt=n$，时间复杂度为$O(log_2n)$。因此，整个算法的时间复杂度为$O(n^2logn+log_2n)$。

空间复杂度

空间瓶颈在于并查集的根节点数组，它的大小是$O(n)$的。而并查集的递归操作对于$O(n)$来说可以忽略，因此整个算法的额外空间复杂度为$O(n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

const int N = 2010, MOD = 1e9 + 7;
int n, m, k, cnt, p[N];

int fast_power(int a, int b, int p) {
    int res = 1 % p;
    while(b) {
        if(b & 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        b >>= 1;
    }
    return res;
}

int find(int x) {
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

void merge(int x, int y) {
    int rx = find(x), ry = find(y);
    if(rx != ry) {
        p[rx] = ry;
        cnt--;
    }
}

int main() {
    scanf("%d%d%d", &n, &m, &k);
    if(k == 1) {
        printf("%d\n", fast_power(m, n, MOD));
        return 0;
    }
    for(int i = 1; i <= n; i++) {
        p[i] = i;
    }
    cnt = n;
    for(int i = 1; i <= n; i++) {
        for(int j = i + 1 + (k&1); j <= min(n, i + k - 1); j += 2) {
            int half = (k - (j - i + 1))>>1;
            if(i - 1 >= half && n - j >= half) {
                merge(i, j);
            }
        }
    }
    printf("%d\n", fast_power(m, cnt, MOD));
    return 0;
}