题目描述

难度分:$2100$

输入$T(\leq 2500)$表示$T$组数据。所有数据的$n$之和$\leq 2500$。

每组数据输入$n$和$k(1 \leq k \leq n \leq 2500)$。

定义【好字符串】为恰好包含一个1的01字符串。

输出有多少个01字符串满足：恰好包含n个好子串，且每个好子串的长度都$\leq k$。答案模$998244353$。

输入样例

6
1 1
3 2
4 2
5 4
6 2
2450 2391

输出样例

1
3
5
12
9
259280854

算法

动态规划

比较容易发现的一点是状态应该是跟$1$旁边有多少个连着的$0$是相关的，但是要设计出这个状态还是很有难度的。

状态定义

$f[i][j]$表示有$i$个好字符串，且这个串的最右边是$j$个连着的$0$，满足这两个条件的字符串个数。在这个定义下，答案就是$\Sigma_{len=0}^{n}f[n][len]$。

状态转移

对于一个串001000，好字符串的左端点可以是左边的001，右端点可以是右边的1000，因此可以贡献$(2+1) \times (3+1)=12$个好字符串。我们可以发现，如果一个串是00001001000，按照这个逻辑考虑完后缀001000（$j=3$），继续往前考虑就会变成一个子问题，接下来就要计算0000100的贡献，此时$j=2$，贡献为$(4+1) \times (2+1)=15$。

这样就得到了状态转移方程

$f[i][r]=\Sigma_{l+r \lt k,(l+1) \times (r+1) \leq i}f[i-(l+1) \times (r+1)][l]$

既要保证下标不为负，还需要保证好字符串的长度在$k$以内，即左边$0$的个数加右边$0$的个数不能达到$k$，否则加上中间的$1$，好字符串的长度就会超过$k$。

复杂度分析

时间复杂度

状态数量为$O(nk)$，单次转移中枚举$l$的次数为$\lfloor \frac{i}{r} \rfloor$。因此运行下来的常数操作是调和级数，而$i$是$O(n)$级别，所以算法整体的时间复杂度为$O(nklnn)$。

空间复杂度

空间消耗就是DP矩阵，是$O(nk)$级别的，由于$k \leq n$，也可以说是$O(n^2)$的。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
const int N = 2510, MOD = 998244353;
int t, n, k, f[N][N];

int dfs(int i, int r) {
    if(i == 0) return 1;
    int &v = f[i][r];
    if(v != -1) {
        return v;
    }
    int res = 0;
    for(int l = 0; l + r < k && (l + 1)*(r + 1) <= i; l++) {
        res = (res + dfs(i - (l + 1)*(r + 1), l)) % MOD;
    }
    return v = res;
}

void solve() {
    scanf("%d%d", &n, &k);
    for(int i = 0; i <= n; i++) {
        for(int j = 0; j <= n; j++) {
            f[i][j] = -1;
        }
    }
    int ans = 0;
    for(int j = 0; j < k; j++) {
        ans = (ans + dfs(n, j)) % MOD;
    }
    printf("%d\n", ans);
}

int main() {
    scanf("%d", &t);
    while(t--) {
        solve();
    }
    return 0;
}