Solution-ABC221H

· · 题解

分拆数做法。

考虑形式化描述问题，计数长度在 k\in[1,n] 的数列 y，满足：

没有第三个条件就是分拆数，有第三个条件的话，只需要在每次转移的时候容斥掉开头恰好有 m+1 个 1 的情况即可。转移方程式：

f_{i,j}=f_{i-1,j-1}+f_{i-j,j}-f_{i-j,j-(m+1)}

解释一下，前面两项就是普通分拆数，最后一项的意思是，如果最开始有 m+1 个 1，那么全局 -1 之后的效果就是删去最开始的 m+1 个数。时间复杂度 \mathcal{O}(n^2)。

PS：可以在这里看博主的完整思考过程，比较有趣。

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define FR first
#define SE second
using namespace std;
inline int read() {
    int x = 0; bool op = 0;
    char c = getchar();
    while(!isdigit(c))op |= (c == '-'), c = getchar();
    while(isdigit(c))x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
    return op ? -x : x;
}
const int N = 5010;
const int P = 998244353;
void add(int &a, int b) {a = (a + b) % P;}
void sub(int &a, int b) {a = (a - b + P) % P;}
int n, m;
int f[N][N], g[N][N];
int main() { 
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    n = read(); m = read();
    f[0][0] = 1;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= i; j++) {
            add(f[i][j], f[i - 1][j - 1]);
            add(f[i][j], f[i - j][j]);
            if(j >= m + 1)sub(f[i][j], f[i - j][j - (m + 1)]);
        }
    }
    for(int i = 1; i <= n; i++)printf("%d\n", f[n][i]);
    return 0;
}