题目大意
有多少个整数序列$A=(A_1,\dots,A_N)$符合如下条件：
- $1\le A_i\le M$
- $\sum\limits_{i=1}^NA_i\le K$
输出答案，对$998244353$取模。
$1\le N,M\le 50$
$N\le K\le NM$
输入格式
$N~M~K$
输出格式
输出答案，对$998244353$取模。
分析
艹C题又要dp
考虑$\text{DP}$思想，令$\text{dp}(i,j):=A$的前$i$个元素中和为$j$的总可能数（$1\le A_x\le M$），则可得伪代码：
1
2
3
4
5
6
|
dp[0][0] = 1
for i = 0 to N-1 // 逐个位置考虑
for j = 0 to K-1 // 考虑所有和的情况，无需考虑K
for k = 1 to M // 1-M的每个选择
if j + k <= K: // 限制条件
dp[i + 1][j + k] += dp[i][j] // 更新dp[i+1]
|
时间复杂度为$\mathcal O(NMK)$，可以通过。
其实还可以利用前缀和优化。
不难发现$\mathrm{dp}(i,j)=\displaystyle\sum_{k=L}^R\text{dp}(i-1,k)$，
其中$L\le R$，具体的值请自行推导。
因此，我们可以记录$\mathrm{dp}[i-1]$的前缀和$\mathrm{pre}$：
- $\mathrm{pre}_j=\displaystyle\sum_{k=1}^j\mathrm{dp}(i-1,k)$
则$\mathrm{dp}(i,j)=\mathrm{pre}_R-\mathrm{pre}_{L-1}$。
因此，时间复杂度为$\mathcal O(NK)$。
强烈建议读者独立推导并实现该方法。 前缀和优化$\text{DP}$的算法在E、F题中很常见。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
#include <cstdio>
#define MOD 998244353
#define maxn 200005
using namespace std;
inline void mod(int& x) { if(x >= MOD) x -= MOD; }
int dp[2][maxn];
int main()
{
int n, m, k;
scanf("%d%d%d", &n, &m, &k);
dp[0][0] = 1;
for(int i=0; i<n; i++)
{
int c = i & 1, p = c ^ 1;
for(int j=0; j<=k; j++)
dp[p][j] = 0;
for(int j=0; j<k; j++)
for(int d=1; d<=m && d<=k-j; d++)
mod(dp[p][j + d] += dp[c][j]);
}
int ans = 0;
for(int i=1; i<=k; i++)
mod(ans += dp[n & 1][i]);
printf("%d\n", ans);
return 0;
}
|
题目大意
给定整数序列$A=(A_1,\dots,A_N)$。
有$Q$个查询。每个查询的格式如下：
- 给定三个整数$L,R,X$，求$A_L,\dots,A_R$中$X$的出现次数。
$1\le A_i,X\le N\le 2\times10^5$
$1\le L\le R\le N$
输入格式
$N$
$A_1~\dots~A_N$
$Q$
$L_1~R_1~X_1$
$\vdots$
$L_Q~R_Q~X_Q$
输出格式
输出$Q$行，第$i$行是第$i$个查询的答案。
分析
题目换句话说就是：求$X$出现的位置中，在$[L,R]$区间内的有多少个？
因此，我们很容易想到先预处理$1,\dots,N$中每个数出现的位置，存入vector，查询时二分即可。
代码
注意二分边界。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
#include <cstdio>
#include <vector>
#include <algorithm>
#define maxn 200005
using namespace std;
vector<int> pos[maxn];
int main()
{
int n, q;
scanf("%d", &n);
for(int i=0; i<n; i++)
{
int a; scanf("%d", &a);
pos[a].push_back(i);
}
scanf("%d", &q);
while(q--)
{
int l, r, x;
scanf("%d%d%d", &l, &r, &x);
printf("%d\n", int(
lower_bound(pos[x].begin(), pos[x].end(), r) -
lower_bound(pos[x].begin(), pos[x].end(), --l)
));
}
return 0;
}
|