問題一覧 > 通常問題

No.1387 Mitarushi's Remodeling

レベル : / AI推定難易度 : 2225 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 13
作問者 : 蜜蜂 / テスター : Mitarushi
お気に入りにしたユーザー ProblemId : 5798 / 自分の提出
問題文最終更新日: 2021-05-17 22:55:15
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
灘高入試コンテスト2021 (順位表) の他の問題:

Problem Statement

One day, Mitsubachi-kun came up with the following problem.

    Divide Card

    Initially, there is one pile of $\ N\ $ stacked cards, and the $\ i\ $-th card from the top of this pile has the integer $\ A_i\ $ written on it.
    You also have a variable $\ S\ $, and currently $\ S=0\ $.

    You will now repeat the following operation exactly $\ K\ $ times. Here, $\ 1 \leq K < N\ $ holds.

      Choose one pile containing $\ Z\ $ cards $\ (2\leq Z)\ $, and call it $\ P\ $. Let $\ Q\ $ be the pile formed by splitting off the top $\ t\ $ cards $\ (1\leq t \leq Z-1)\ $ of $\ P\ $ while preserving their order, and let the pile of the remaining $\ Z-t\ $ cards be the new $\ P\ $.
      When the split is finished, let $\ X\ $ be the sum of the numbers written on the cards in $\ P\ $ and $\ Y\ $ be the sum of the numbers written on the cards in $\ Q\ $, and add $\ X \times Y\ $ to $\ S\ $.

    There are $\ (N-1) \times (N-2) \times \cdots \times (N-K)\ $ possible ways to perform the operations. Find the sum of the values of $\ S\ $ after the operations over all of them.

    Here, $2\ $ sequences of $\ K\ $ operations are considered different if there exists an integer $\ i(1 \leq j \leq K)\ $ such that the following holds after the $i\ $-th operation.

      There exist integers $\ l,m(1 \leq l < m \leq N)\ $ such that, in one of them, the cards originally $\ l\ $-th and $\ m\ $-th from the top are in the same pile, while in the other they are not in the same pile.

However, this was too easy for Mitarushi-kun, so the following changes were made.

    Mitarushi's Remodeling

    You are given integers $\ N^\prime ,K^\prime\ $ and $\ N^\prime\ $ positive integers $\ M_1,M_2, \cdots ,M_{N^\prime}\ $.
    There are $\ K^\prime \times M_1 \times M_2 \times \cdots \times M_{N^\prime}\ $ inputs of Divide Card satisfying "$\ N=N^\prime\ $ and $\ 1 \leq K \leq K^\prime\ $ and $\ 1 \leq A_i \leq M_i\ $ for every integer $\ i\ $ between $\ 1\ $ and $\ N^\prime\ $, inclusive". Find the sum of the answers to Divide Card over all of them.

    Since the answer can be large, output it modulo $\ 998244353\ $.

Solve Mitarushi's Remodeling.

Input

$N^\prime\ \ K^\prime$
$M_1\ \ M_2\ \ \cdots \ \ M_{N^\prime}$

  • $1 \leq K^\prime < N^\prime \leq 5\times 10^5$
  • $1 \leq M_i \leq 10^9(1 \leq i \leq N^\prime)$
  • All inputs are integers.

Output

Output the answer to Mitarushi's Remodeling, followed by a newline. Note that you must output it modulo $\ 998244353\ $.

Sample

Sample 1
Input
3 1
1 1 2
Output
11

The possible values of $\ N,K,A_i\ $ for the input of Divide Card are the following $\ 2\ $ cases: $\ N=3,K=1,A_1=1,A_2=1,A_3=1\ $ and $\ N=3,K=1,A_1=1,A_2=1,A_3=2\ $.
Consider the former input.

Let the $\ 3\ $ stacked cards in the initial pile be $\ X,Y,Z\ $ from the top ($\ A_1,A_2,A_3\ $ are written on $\ X,Y,Z\ $, respectively).

For the $1\ $st operation, the following $\ 2\ $ ways are possible.

・Split the pile into $\ 2\ $ piles: a pile consisting of $\ X\ $ and a pile consisting of $\ Y,Z\ $.
・Split the pile into $\ 2\ $ piles: a pile consisting of $\ X,Y\ $ and a pile consisting of $\ Z\ $.

Note that after the $1\ $st of these operations, the pile consisting of $\ Y,Z\ $ has $\ Y\ $ on top.
Also note that an operation splitting the pile into $\ 2\ $ piles, a pile consisting of $\ X,Z\ $ and a pile consisting of $\ Y\ $, is not allowed.

If the $1\ $st operation is performed, $\ 1\times(1+1)\ $ is added to $\ S\ $, resulting in $\ S=2\ $.
If the $2\ $nd operation is performed, $\ (1+1)\times1\ $ is added to $\ S\ $, resulting in $\ S=2\ $.

Therefore, the answer to Divide Card for this input is $\ 2+2=4\ $.

Similarly, the answer to Divide Card for the other input turns out to be $\ 7\ $.
Thus, the answer to Mitarushi's Remodeling is $\ 4+7=11\ $.

Sample 2
Input
7 6
20 21 2 10 2 11 76
Output
249962858

After the high school entrance exams held in the year $\ 2021\ $, in month $\ 2\ $ on day $\ 10\ $ and in month $\ 2\ $ on day $\ 11\ $, the $\ 76\ $th class of Nada School will enroll.
In contrast to the "Zairai" students, who have been there since junior high school, they are called "Shinko".

Sample 3
Input
10 7
31415 92653 58979 32384 62643 38327 95028 84197 16939 93751
Output
666468393

Output the answer modulo $\ 998244353\ $.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。