第三届 AtCoder Japan Open -预选-（第 232 场 AtCoder Regular Contest++）
删除不同元素AI (CI翻译)
Problem Statement
题目描述
AI (CI翻译)You are given integers $N$ and $K$.
给定整数 $N$ 和 $K$。AI (CI翻译)
For an integer sequence $S$ consisting of integers between $1$ and $K$, inclusive, define its score $f(S)$ as follows.
对于一个由 $1$ 至 $K$ 之间（含）的整数构成的整数序列 $S$，定义其得分 $f(S)$ 如下。AI (CI翻译)
- Repeat the following operation until all elements of
$S$are equal. The number of times this operation is performed is$f(S)$. - Let
$|S|$be the length of$S$before the operation. For every$i$satisfying$2 \leq i \leq |S|$and$S_{i-1} \ne S_i$, simultaneously delete the$i$-th element of$S$. Concatenate the remaining elements in their original order to form the new$S$.
- 重复执行以下操作，直到
$S$中的所有元素都相等。该操作执行的次数即为$f(S)$。 - 设操作前
$S$的长度为$|S|$。对于满足$2 \leq i \leq |S|$且$S_{i-1} \ne S_i$的每个$i$，同时删除$S$的第$i$个元素。将剩余元素按原顺序连接，得到新的$S$。
There are $K^N$ integer sequences $S$ of length $N$ consisting of integers between $1$ and $K$, inclusive. Find the sum of $f(S)$ over all of them, modulo $998244353$.
共有 $K^N$ 个长度为 $N$、由 $1$ 至 $K$ 之间（含）的整数构成的整数序列 $S$。求所有这些序列的 $f(S)$ 之和，结果对 $998244353$ 取模。AI (CI翻译)
Constraints
约束条件
AI (CI翻译)$2 \leq N \leq 100$$2 \leq K < 998244353$- All input values are integers.
$2 \leq N \leq 100$$2 \leq K < 998244353$- 所有输入值均为整数。
Input
输入格式
AI (CI翻译)The input is given from Standard Input in the following format:
输入从标准输入按以下格式给出：AI (CI翻译)
N KN KOutput
输出格式
AI (CI翻译)Output the answer.
输出答案。AI (CI翻译)
样例
Input #1
3 2
Output #1
8
The scores of $(1,1,1)$ and $(2,2,2)$ are $0$, and the scores of $(1,2,2)$ and $(2,1,1)$ are $2$. The scores of the other four sequences are $1$, so the sum is $8$.
Input #2
6 2
Output #2
126
For example, $S=(1,2,2,2,1,2)$ changes as follows, so its score is $3$.
$(1,2,2,2,1,2) \to (1,2,2) \to (1,2) \to (1)$
Input #3
2 2
Output #3
2
Input #4
10 3
Output #4
145002
Input #5
100 998244352
Output #5
139448523
题目信息
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（gpt-6.1-sol），如有出入请以原文为准。