[AT4362] [ARC102C] Stop. Otherwise...

· · 题解

首先考虑对于单个 x~(x\in[2,2K]) 可以怎么求。

对于点数 i~(i\in[1,K]) 进行分情况讨论。

接下来考虑 dp。

设 f(i,j) 表示考虑了 i 对数（不考虑 x-i=i 的情况），其中选择了 j 个数的组成的集合个数，很容易想到：

f(i,j)=f(i-1,j)+2 \times \sum_{k=1}^j f(i-1,j-k)

同样的，设 g(i,j) 表示考虑了 i 个没有限制的数，其中选择了 j 个数组成的集合数，同理可以得到：

g(i,j)=\sum_{k=0}^j g(i-1,j-k)

上述两个 dp 都可以使用前缀和优化。

接着对于每一个 x，求出满足三个条件的数各有多少个，然后将各自的方案数乘起来就行了。

#include <bits/stdc++.h>
#define LL long long

using namespace std;

const int maxn = 2e3 + 5;
const LL MOD = 998244353;

int n, m;
LL f[maxn][maxn], g[maxn][maxn];

int main() {
    scanf("%d%d", &m, &n);
    f[0][0] = g[0][0] = 1;
    LL s0, s1;
    for (int i = 1; i <= m; i++) {
        s0 = s1 = 0;
        for (int j = 0; j <= n; j++)
            f[i][j] = (f[i - 1][j] + s0 * 2 % MOD) % MOD,
            s0 = (s0 + f[i - 1][j]) % MOD,
            g[i][j] = (g[i - 1][j] + (j > 0 ? g[i][j - 1] : 0)) % MOD;
    }
    for (int i = 2; i <= (m << 1); i++) {
        int c1 = 0, c2 = (i % 2 == 0), c3; LL ans = 0;
        for (int j = 1; j <= m; j++) c1 += (i - j > m || i - j <= 0);
        c3 = (m - c1 - c2) >> 1;
        for (int j = 0; j <= n; j++) ans = (ans + f[c3][j] * g[c1][n - j] % MOD) % MOD;
        if (c2) for (int j = 0; j < n; j++) ans = (ans + f[c3][j] * g[c1][n - j - 1] % MOD) % MOD;
        printf("%lld\n", ans);
    }
    return 0;
}