有多少个长度为N的整数序列，满足以下条件：1<=Ai<=M 且 |Ai-A_{i+1}| >=k 你需要模998244353.

根据题意，每个位置的数的取值范围是 [1, M]，且相邻两个数的差的绝对值不小于 k。我们可以考虑使用 dp 来解决这个问题。

令 f[i][j] 表示长度为 i，最后一个数为 j 的方案数。转移时，我们需要将前一个数的取值 j' 与当前数的取值 j 进行比较，如果满足条件，则可以转移：

f[i][j] = \sum_{j'=1}^M [abs(j-j') \geq k] f[i-1][j']

最终的答案是 f[N][1]+f[N][2]+...+f[N][M]。由于每次转移需要枚举 M 个数，因此总时间复杂度为 O(NM^2)。

实际上，我们可以使用前缀和优化这个过程，将时间复杂度优化到 O(NM)。具体来说，我们可以预处理出 f[i-1][j'] 中满足 abs(j-j') < k 的部分的前缀和，然后在计算 f[i][j] 时直接用前缀和计算即可。

相关问题

c++代码 给定一个长度为n(n<=1e5)的序列a和一个整数k(k<=1e5)，请对于每个1<=i<=n，求出对应的1<=j<=n，使得ai异或aj第k大。 你需要输出这aj的值。

这是一个比较典型的异或问题，可以使用字典树来解决。具体思路如下：

1. 预处理出数组中任意两个数异或的结果，并将这些结果插入到字典树中。

2. 对于每个数a[i]，在字典树中查找异或结果中第k大的数，即可得到对应的aj的值。

以下是对应的C++代码实现：

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;

int n, k, tot;
int a[N], trie[N * 30][2], cnt[N * 30];

void insert(int x) {
    int p = 0;
    for (int i = 30; i >= 0; i--) {
        int u = (x >> i) & 1;
        if (!trie[p][u]) trie[p][u] = ++tot;
        p = trie[p][u];
        cnt[p]++;
    }
}

int query(int x) {
    int p = 0, res = 0;
    for (int i = 30; i >= 0; i--) {
        int u = (x >> i) & 1, v = k >> i & 1;
        if (v) {
            if (trie[p][u ^ 1] && cnt[trie[p][u ^ 1]] >= v) {
                p = trie[p][u ^ 1];
                res |= (u ^ 1) << i;
            } else {
                p = trie[p][u];
                res |= u << i;
            }
        } else {
            if (trie[p][u] && cnt[trie[p][u]] >= v) {
                p = trie[p][u];
                res |= u << i;
            } else {
                p = trie[p][u ^ 1];
                res |= (u ^ 1) << i;
            }
        }
    }
    return res;
}

int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        insert(a[i]);
    }
    for (int i = 1; i <= n; i++) {
        printf("%d ", query(a[i]));
    }
    return 0;
}

时间复杂度为O(nlogk)。

C++代码 给定一个长度为n（n<=1e5）的序列a和一个整数k（k<=1e5），请对于每个1<=i<=n，求出对应的1<=j<=n，使得ai异或aj第k大。你需要输出这aj的值。输入6 2 1 1 4 5 1 4 输出5 5 5 4 5 5

这是一个比较典型的异或问题，可以使用字典树来解决。具体思路如下：

1. 预处理出数组中任意两个数异或的结果，并将这些结果插入到字典树中。

2. 对于每个数a[i]，在字典树中查找异或结果中第k大的数，即可得到对应的aj的值。

以下是对应的C++代码实现：

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;

int n, k, tot;
int a[N], trie[N * 30][2], cnt[N * 30];

void insert(int x) {
    int p = 0;
    for (int i = 30; i >= 0; i--) {
        int u = (x >> i) & 1;
        if (!trie[p][u]) trie[p][u] = ++tot;
        p = trie[p][u];
        cnt[p]++;
    }
}

int query(int x) {
    int p = 0, res = 0;
    for (int i = 30; i >= 0; i--) {
        int u = (x >> i) & 1, v = k >> i & 1;
        if (v) {
            if (trie[p][u ^ 1] && cnt[trie[p][u ^ 1]] >= v) {
                p = trie[p][u ^ 1];
                res |= (u ^ 1) << i;
            } else {
                p = trie[p][u];
                res |= u << i;
            }
        } else {
            if (trie[p][u] && cnt[trie[p][u]] >= v) {
                p = trie[p][u];
                res |= u << i;
            } else {
                p = trie[p][u ^ 1];
                res |= (u ^ 1) << i;
            }
        }
    }
    return res;
}

int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        insert(a[i]);
    }
    for (int i = 1; i <= n; i++) {
        printf("%d ", query(a[i]));
    }
    return 0;
}

时间复杂度为O(nlogk)。