No.3771 Leq-K Partition Multiplied
タグ : / 解いたユーザー数 7
作問者 :
apricity
/ テスター :
kaichou243
Problem Statement
You are given positive integers $N,M,K,X$.
For an integer sequence $A$, let $f(A)$ be the answer to the following problem.
Consider partitioning $A$ into non-empty contiguous subsequences. Each element of $A$ must belong to exactly $1$ subsequence. Find the minimum number of subsequences required for a partition in which the number of distinct values appearing in every subsequence is at most $K$.
There are $M^n$ possible integer sequences $A$ of length $n$ consisting of integers between $1$ and $M$, inclusive. Let $S_n$ be the sum of $f(A)^X$ over all of them.
For each of $n = 1,2,\dots,N$, find $S_n$ modulo $998244353$.
Input
$N\ M\ K\ X$
- All input values are integers.
- $1 \leq N \leq 2\times 10^5$
- $1 \leq M \leq 10^{18}$
- $1 \leq K \leq 2\times 10^5$
- $1 \leq X \leq 10^{18}$
Output
Print $N$ lines. On the $n$-th line, print $S_n$ modulo $998244353$.
Sample
Sample 1
Input
3 3 2 1
Output
3 9 33
Consider the case $n=3$.
- $(1,2,3)$ can be partitioned into $2$ subsequences, as in $(1,2), (3)$.
- $(1,2,2)$ can be partitioned into $1$ subsequence, as in $(1,2,2)$.
There are $3^3=27$ possible sequences $A$. Among them, the permutations of $(1,2,3)$ ($6$ sequences) have $f(A) = 2$, and all the others ($21$ sequences) have $f(A) = 1$. Therefore, $S_3 = 6\times 2^1 + 21 \times 1^1 = 33$.
Sample 2
Input
4 2 3 2
Output
2 4 8 16
Sample 3
Input
10 122333444455555 3 9876543210
Output
595484111 116899793 297334529 660167065 603008404 232613563 68193567 936419468 625547368 48824042
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。