問題一覧 > 通常問題

No.1923 Divisor Array

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 9
作問者 : ebi_fly
お気に入りにしたユーザー ProblemId : 8083 / 自分の提出
問題文最終更新日: 2022-05-01 23:50:22
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. Show the original

Problem Statement

You are given positive integers $N,M,K$. Let $D$ be the product of the $K$ smallest prime numbers. How many sequences $A = (A_0, A_1, \dots, A_N)$ of length $N+1$ satisfy the following conditions? Output the answer modulo $998244353$.

Conditions

  • $A_0 = D$
  • For $i = 1,\dots,N$, $A_i$ is a positive divisor of $\displaystyle\prod_{j = 0}^{i-1}A_j$.
  • The number of positive divisors of $\displaystyle\prod_{i = 1}^{N}A_i$ is at most $M$.

Input

$N$ $M$ $K$
  • $1 \leq N \leq 10^9$
  • $1 \leq M \leq 2000$
  • $1 \leq K \leq 10^9$
  • All values in the input are integers.

Output

Output the answer modulo $998244353$.

Sample

Sample 1
Input
2 2 2
Output
5

Since $K=2$, we have $D=2\times3$. In this case, the following $5$ sequences $A$ of length $3$ satisfy the conditions.

  • $(A_0,A_1,A_2) = (6,1,1)$
  • $(A_0,A_1,A_2) = (6,1,2)$
  • $(A_0,A_1,A_2) = (6,2,1)$
  • $(A_0,A_1,A_2) = (6,1,3)$
  • $(A_0,A_1,A_2) = (6,3,1)$
Sample 2
Input
3 3 4
Output
25
Sample 3
Input
1000000000 2000 1000000000
Output
362056892

Note that you should output the answer modulo $998244353$.

Source: CPCTF22

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