AT_abc279_h [ABC279Ex] Sum of Prod of Min

题目描述

给定正整数 $N, M$，其中保证 $N \leq M \leq 2N$。

对于所有满足 $\displaystyle \sum_{i=1}^{N} S_i = M$ 的正整数序列 $S = (S_1, S_2, \dots, S_N)$，请计算以下值，并输出它们的总和对质数 $200003$ 取模的结果（注意本题的 $\bmod$ 值与通常不同）。

• $\displaystyle \prod_{k=1}^{N} \min(k, S_k)$

输入格式

输入从标准输入中以以下格式给出。

$N$ $M$

输出格式

请输出答案的整数值。

输入输出样例 #1

输入 #1

3 5

输出 #1

14

输入输出样例 #2

输入 #2

1126 2022

输出 #2

40166

输入输出样例 #3

输入 #3

1000000000000 1500000000000

输出 #3

180030

说明/提示

限制条件

• $1 \leq N \leq 10^{12}$
• $N \leq M \leq 2N$
• 输入均为整数

样例解释 1

满足条件的 $S$ 有 $S=(1,1,3),\ S=(1,2,2),\ S=(1,3,1),\ S=(2,1,2),\ S=(2,2,1),\ S=(3,1,1)$ 共 $6$ 种。对于每个 $S$，$\displaystyle \prod_{k=1}^{N} \min(k, S_k)$ 的值分别为：

• $S=(1,1,3)$：$1 \times 1 \times 3 = 3$
• $S=(1,2,2)$：$1 \times 2 \times 2 = 4$
• $S=(1,3,1)$：$1 \times 2 \times 1 = 2$
• $S=(2,1,2)$：$1 \times 1 \times 2 = 2$
• $S=(2,2,1)$：$1 \times 2 \times 1 = 2$
• $S=(3,1,1)$：$1 \times 1 \times 1 = 1$

因此，总和为 $14$，输出 $14$。

样例解释 2

请输出总和对 $200003$ 取模的结果。

由 ChatGPT 4.1 翻译