[ABC253E] Distance Sequence Solution

更好的阅读体验戳此进入

题面

给定 $n,m,k$$n, m, k$，求有多少序列 $a_n$$a_n$，满足：

• $1\le a_i\le m(1\le i\le m)$$1 \le a_i \le m (1 \le i \le m)$。
• $|a_i-a_{i+1}|\ge k(1\le i\le n-1)$$\lvert a_i - a_{i + 1} \rvert \ge k (1 \le i \le n - 1)$。

Solution

一看题意和数据范围，DP 显然，不难想到设状态 $dp(i,j)$$dp(i, j)$ 为长度为 $i$$i$ 的以 $j$$j$ 为结尾的合法序列的方案数。也不难想到一个 $\mathtt{\text{2D1D}}$$\texttt{2D1D}$ 的转移，即：

同时注意转移前需要判断是否满足 $j+k\le m$$j + k \le m$ 和 $j-k\ge 1$$j - k \ge 1$。然后这个式子也很显然可以前缀和优化成 $\mathtt{\text{2D0D}}$$\texttt{2D0D}$，最后复杂度也就是 $O(nm)$$O(nm)$ 的。然后滚动数组也可以压掉一维，不过没必要，空间开的下。

然后按照这个做完会发现 WA 了两个点，具体看一下就会发现，按照这个式子，如果 $k=0$$k = 0$，那么 $dp(i-1,j)$$dp(i - 1, j)$ 就会被加两次，所以此时还需要特判一下减去一个 $dp(i-1,j)$$dp(i - 1, j)$。

Code

xxxxxxxxxx
61
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
using namespace std;
12

13
mt19937 rnd(random_device{}());
14
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
15
bool rnddd(int x){return rndd(1, 100) <= x;}
16

17
typedef unsigned int uint;
18
typedef unsigned long long unll;
19
typedef long long ll;
20
typedef long double ld;
21

22
#define MOD (ll)(998244353ll)
23

24
template < typename T = int >
25
inline T read(void);
26

27
int N, M, K;
28
ll dp[1100][5100];
29
ll sum[5100];
30

31
int main(){
32
    N = read(), M = read(), K = read();
33
    for(int i = 1; i <= M; ++i)dp[1][i] = 1, sum[i] = i;
34
    for(int i = 2; i <= N; ++i){
35
        for(int j = 1; j <= M; ++j){
36
            (dp[i][j] += j + K <= M ? (sum[M] - sum[j + K - 1] + MOD) % MOD : 0) %= MOD;
37
            (dp[i][j] += j - K >= 1 ? sum[j - K] : 0) %= MOD;
38
            if(!K)(dp[i][j] += -(sum[j] - sum[j - 1]) + MOD) %= MOD;
39
        }
40
        for(int j = 1; j <= M; ++j)
41
            sum[j] = (sum[j - 1] + dp[i][j]) % MOD;
42
    }printf("%lld\n", sum[M]);
43
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
44
    return 0;
45
}
46

47
template < typename T >
48
inline T read(void){
49
    T ret(0);
50
    int flag(1);
51
    char c = getchar();
52
    while(c != '-' && !isdigit(c))c = getchar();
53
    if(c == '-')flag = -1, c = getchar();
54
    while(isdigit(c)){
55
        ret *= 10;
56
        ret += int(c - '0');
57
        c = getchar();
58
    }
59
    ret *= flag;
60
    return ret;
61
}

UPD

update-2022_12_05 初稿