有多少个长度为N的整数序列,满足以下条件:1<=Ai<=M 且 |Ai-A_{i+1}| >=k 你需要模998244353.(1\leq N \leq 2000,1\leq M\leq 5000,1\leq K \leq M-1)
时间: 2023-11-23 16:07:20 浏览: 54
根据题意,每个位置的数的取值范围是 [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] 时直接用前缀和计算即可。
下面是代码实现:
相关问题
有多少个长度为N的整数序列,满足以下条件:1<=Ai<=M 且 |Ai-A_{i+1}| >=k 你需要模998244353.
这是一个典型的数位DP问题。我们可以用dp[i][j]表示已经填了前i个数字,最后一位是j方案数。由于每个数位的取值范围是1~M,因此状态的第二维可以用M来表示。转移方程如下:
dp[i][j] = ∑dp[i-1][p] (1<=p<=M, |p-j|>=k)
最终的答案就是dp[N][1]~dp[N][M]的总和。注意,由于需要模998244353,所以在计算过程中需要取模。
下面是完整的代码实现:
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++代码实现:
```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)。
相关推荐
![text/x-c](https://img-home.csdnimg.cn/images/20210720083646.png)
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![md](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![txt](https://img-home.csdnimg.cn/images/20210720083642.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)