102797: [AtCoder]ABC279 Ex - Sum of Prod of Min
Description
Score : $600$ points
Problem Statement
You are given positive integers $N$ and $M$. Here, it is guaranteed that $N\leq M \leq 2N$.
Print the sum, modulo $200\ 003$ (a prime), of the following value over all sequences of positive integers $S=(S_1,S_2,\dots,S_N)$ such that $\displaystyle \sum_{i=1}^{N} S_i = M$ (notice the unusual modulo):
- $\displaystyle \prod_{k=1}^{N} \min(k,S_k)$.
Constraints
- $1 \leq N \leq 10^{12}$
- $N \leq M \leq 2N$
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
$N$ $M$
Output
Print the answer as an integer.
Sample Input 1
3 5
Sample Output 1
14
There are six sequences $S$ that satisfy the condition: $S=(1,1,3), S=(1,2,2), S=(1,3,1), S=(2,1,2), S=(2,2,1), S=(3,1,1)$.
The value $\displaystyle \prod_{k=1}^{N} \min(k,S_k)$ for each of those $S$ is as follows.
- $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$
Thus, you should print their sum: $14$.
Sample Input 2
1126 2022
Sample Output 2
40166
Print the sum modulo $200\ 003$.
Sample Input 3
1000000000000 1500000000000
Sample Output 3
180030
Input
题意翻译
定义长度为 $N$ 的正整数数组 $S$ 的权值为 $\prod_i \min(i,S_i)$，求所有满足 $\sum_i S_i=M$ 的数组的权值和，对 $200003$ 取模。 $N\le M\le 2N$，$N\le 10^{12}$。Output
问题描述
给你两个正整数$N$和$M$。其中，保证了$N\leq M \leq 2N$。
对于所有满足$\displaystyle \sum_{i=1}^{N} S_i = M$（注意不寻常的模）的正整数序列$S=(S_1,S_2,\dots,S_N)$，求以下值的和，取模$200\ 003$（一个质数）：
- $\displaystyle \prod_{k=1}^{N} \min(k,S_k)$。
约束条件
- $1 \leq N \leq 10^{12}$
- $N \leq M \leq 2N$
- 输入中的所有值都是整数。
输入
输入数据通过标准输入以以下格式给出：
$N$ $M$
输出
输出一个整数作为答案。
样例输入1
3 5
样例输出1
14
有六个满足条件的序列$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)$
对于这些$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$。
样例输入2
1126 2022
样例输出2
40166
输出模$200\ 003$的和。
样例输入3
1000000000000 1500000000000
样例输出3
180030