Translation Notice
This article was machine-translated using DeepSeek-R1.

• Original Version: Authored in Chinese by myself
• Accuracy Advisory: Potential discrepancies may exist between translations
• Precedence: The Chinese text shall prevail in case of ambiguity
• Feedback: Technical suggestions regarding translation quality are welcomed

C - Dice Sum

Problem Statement

How many integer sequences $A=(A_1,\dots,A_N)$ satisfy the following conditions:

• $1\le A_i\le M$
• $\sum\limits_{i=1}^NA_i\le K$

Output the answer modulo $998244353$.

$1\le N,M\le 50$
$N\le K\le NM$

Input Format

$N~M~K$

Output Format

Print the answer modulo $998244353$.

Analysis

Damn, another DP problem for C

We use dynamic programming. Let $\text{dp}(i,j)$ denote the number of valid sequences for the first $i$ elements with sum $j$ ($1\le A_x\le M$). The pseudocode is as follows:

1
2
3
4
5
6

dp[0][0] = 1
for i = 0 to N-1 // consider each position one by one
    for j = 0 to K-1 // consider all possible sums (up to K-1)
        for k = 1 to M // each choice from 1-M
            if j + k <= K: // constraint
                dp[i + 1][j + k] += dp[i][j] // update dp[i+1]

Time complexity is $\mathcal O(NMK)$, which is acceptable.

Actually, prefix sum optimization can be applied.
We observe that $\mathrm{dp}(i,j)=\displaystyle\sum_{k=L}^R\text{dp}(i-1,k)$,
where $L\le R$. The exact values of $L$ and $R$ are left for derivation.
We can precompute the prefix sum $\mathrm{pre}$ of $\mathrm{dp}[i-1]$:

• $\mathrm{pre}_j=\displaystyle\sum_{k=1}^j\mathrm{dp}(i-1,k)$

Then $\mathrm{dp}(i,j)=\mathrm{pre}_R-\mathrm{pre}_{L-1}$.
This reduces the time complexity to $\mathcal O(NK)$.
Readers are strongly encouraged to derive and implement this optimization. Prefix-sum optimized DP is common in problems like E and F.

Code

 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;
}

D - Range Count Query

Problem Statement

Given an integer sequence $A=(A_1,\dots,A_N)$.
Process $Q$ queries. Each query is formatted as:

• Given integers $L,R,X$, count the occurrences of $X$ in $A_L,\dots,A_R$.

$1\le A_i,X\le N\le 2\times10^5$
$1\le L\le R\le N$

Input Format

$N$
$A_1~\dots~A_N$
$Q$
$L_1~R_1~X_1$
$\vdots$
$L_Q~R_Q~X_Q$

Output Format

Print $Q$ lines, each containing the answer to a query.

Analysis

The problem reduces to: For each $X$, count how many of its positions lie within $[L,R]$.
Thus, we preprocess the positions where each number appears using a vector, then answer queries via binary search.

Code

Note the binary search boundaries.

 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;
}