No.2670 Sum of Products of Interval Lengths
タグ : / 解いたユーザー数 27
作問者 :
cureskol
Problem Statement
You are given positive integers $n,m$.
For an integer sequence $A = (A _ 1, A _ 2, \ldots, A _ n)$ of length $n$ whose elements are all integers between $1$ and $m$, inclusive, a pair of integers $(l,r)$ satisfying $1\leq l\leq r\leq n$ is called a good pair if the following holds.
- $A _ {l + i} = A _ l + i$ holds for all $i = 0, 1, \ldots, r - l$
Also, an integer sequence $(x _ 1, x _ 2, \ldots, x _ k)$ is called a good sequence if both of the following $2$ conditions hold.
- $1 = x _ 1\lt x _ 2\lt \cdots \lt x _ k = n + 1$
- For all $i = 1,2,\ldots,k - 1$, the pair $(x _ i, x _ {i + 1} - 1)$ is a good pair
It can be proved that for any $A$, the good sequence $x$ of minimum length is uniquely determined; denote it by $x ^ \ast = (x ^ \ast _ 1, x ^ \ast _ 2, \ldots, x ^ \ast _ k)$. Then, the score $f(A)$ of $A$ is defined as follows.
$$f(A)\coloneqq\prod _ {i = 1} ^ {k - 1} (x ^ \ast _ {i + 1} - x ^ \ast _ i).$$
There are $m ^ n$ integer sequences $A$ of length $n$ whose elements are all integers between $1$ and $m$, inclusive. Find the sum of the scores over all of them, modulo $998244353$.
Input
The input is given from standard input in the following format.
$n\ m$
- All input values are integers.
- $1\leq n\leq 2\times 10 ^ 5$
- $1\leq m\leq 10 ^ {18}$
Output
Print the answer on $1$ line, followed by a newline.
Sample
Sample 1
Input
3 2
Output
12
This input represents $n=3,\ m=2$. There are $8$ possible sequences $A$: $(1,1,1),\ (1,1,2),\ (1,2,1),\ (1,2,2),\ (2,1,1),\ (2,1,2),\ (2,2,1),\ (2,2,2)$.
For example, for $A = (1,1,2)$, there are $2$ good sequences, $x = (1,2,3,4)$ and $x = (1,2,4)$, and the one of minimum length is $x ^ \ast = (1,2,4)$. Therefore, the score of this $A$ is $(2 - 1) \times (4 - 2) = 2$.
It can be verified that the scores of $(1,1,1),\ (1,1,2),\ (1,2,1),\ (1,2,2),\ (2,1,1),\ (2,1,2),\ (2,2,1),\ (2,2,2)$ are $1,2,2,2,1,2,1,1$, respectively, so print their sum, $12$, as the answer.
Sample 2
Input
200000 1000000000000000000
Output
156232207
Print the sum of the scores modulo $998244353$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。