No.2952 Invision of Multiples
レベル :
/ AI推定難易度 : 2500
/ 実行時間制限 : 1ケース 4.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 20
作問者 :
nouka28
/ テスター :
とりゐ
t9unkubj
rotti_coder
Michirakara
タグ : / 解いたユーザー数 20
作問者 :
nouka28
/ テスター :
とりゐ
t9unkubj
rotti_coder
Michirakara
問題文最終更新日: 2024-10-01 22:46:05
English (AI translation)
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
Problem Statement
You are given positive integers $N,M$ and a sequence of positive integers $D=(D_1,D_2,\dots,D_N)$.
Find the sum of the inversion numbers over all sequences of positive integers $A=(A_1,A_2,\dots,A_N)$ satisfying the following conditions, modulo $998244353$.
- $1\leq A_i\leq M(1\leq i\leq N)$
- For each $i$ $(1\leq i\leq N)$, $A_i$ is a multiple of $D_i$
What is the inversion number?
The inversion number of a sequence $X=(X_1,X_2,\dots,X_{|X|})$ is the number of pairs of integers $(i,j)(1\leq i< j\leq |X|)$ satisfying $A_i>A_j$.
Constraints
- $2\leq N\leq 5\times 10^4$
- $1\leq M\leq 5\times 10^4$
- $1\leq D_i\leq M$
- All input values are integers
Input
$N$ $M$ $D_1$ $D_2$ $\dots$ $D_N$
Output
Output the answer.
Sample
Sample 1
Input
4 7 3 2 5 4
Output
19
There are $6$ sequences $A$ satisfying the conditions, as follows.
- When $A=(3,2,5,4)$, the inversion number is $2$.
- When $A=(3,4,5,4)$, the inversion number is $1$.
- When $A=(3,6,5,4)$, the inversion number is $3$.
- When $A=(6,2,5,4)$, the inversion number is $4$.
- When $A=(6,4,5,4)$, the inversion number is $4$.
- When $A=(6,6,5,4)$, the inversion number is $5$.
Therefore, the answer is $2+1+3+4+4+5=19$.
Sample 2
Input
2 1 1 1
Output
0
Sample 3
Input
10 50000 1 2 3 4 5 6 7 8 9 10
Output
292979039
Find the remainder when divided by $998244353$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。