自动搬运

查看原文

来自洛谷，原作者为

	sunkuangzheng **

搬运于2025-08-24 23:12:50，当前版本为作者最后更新于2025-04-10 18:01:57，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

首先对题面做第一步转化：我们不关心最长公共子串的具体值，只关心它是否大于等于 $k+1$。而公共子串长度有单调性，因此我们只关心是否存在长度为 $k+1$ 的公共子串。因此问题转化为：求有多少 $s,t$ 满足存在公共子串 $w$ 且不存在长度为 $k+1$ 的公共子串。

注意到 $2^{k+1} = 16$ 非常小，我们可以把所有的 $2^{k+1}$ 个子串是否出现过压进状态。一开始我在想对两个串同时进行 dp，但是时空复杂度都爆炸。后来发现两个串的填充是基本独立的，我们只需要保证其最后拥有的 $2^{k+1}$ 子串不交。

那么进行 DP，设 $dp_{n,o,r,b}$ 表示长度为 $n$，串的最后 $k$ 个字符是 $o$，串中是否存在了 $w$ 的状态是 $r=0/1$，串中拥有的所有 $2^{k+1}$ 子串的状态是 $b$ 的方案数，转移直接枚举填什么就行了。

然后最终的问题是，求 $\sum \limits_{i \& j = 0} f_ig_j$，这是套路的，考虑对 $g$ 数组的下标反转（$0111 \to 1000$），这样限制就变成了 $g$ 是 $i$ 的超集，高维前缀和即可。

/**
 *    author: sunkuangzheng
 *    created: 19.11.2024 08:47:52
**/
#include<bits/stdc++.h>
#ifdef DEBUG_LOCAL
#include <mydebug/debug.h>
#endif
using ll = long long;
const int N = 5e5+5,mod = 998244353;
using namespace std;
int T,n,M,k,w,dp[105][8][2][1 << 16],m,len; string s;
void ad(int &x,int y){x = (x + y) % mod;}
vector<int> get(int n){
    vector<int> f(len);
    for(int o = 0;o < m;o ++) for(int j = 0;j < len;j ++) ad(f[j],dp[n][o][1][j]);
    return f; 
}int main(){
    ios::sync_with_stdio(0),cin.tie(0);
    cin >> n >> M >> k >> s;
    for(char c : s) w = w * 2 + c - '0';
    m = (1 << k),len = (1 << m * 2);
    for(int i = 0;i < m;i ++) dp[k][i][(i == w)][0] = 1;
    for(int i = k;i < max(n,M);i ++) for(int o = 0;o < m;o ++) for(int r : {0,1})
        for(int b = 0;b < len;b ++) for(int j : {0,1}){
            int nw = o * 2 + j;
            // if(dp[i][o][r][b]) debug(i,o,r,b),debug(i+1,nw%m,r|(nw%m==w),b|(1<<nw));
            ad(dp[i+1][nw%m][r|(nw%m==w)][b|(1<<nw)],dp[i][o][r][b]);
        }
    auto f = get(n),g = get(M);
    reverse(g.begin(),g.end());
    for(int i = 0;i < m * 2;i ++) for(int j = len - 1;j >= (1 << i);j --)
        if(j >> i & 1) ad(g[j - (1 << i)],g[j]);
    int ans = 0;
    for(int i = 0;i < len;i ++) ad(ans,1ll * f[i] * g[i] % mod);
    cout << ans << "\n"; 
}