102797: [AtCoder]ABC279 Ex - Sum of Prod of Min

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

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

得分:$600$分

问题描述

给你两个正整数$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

加入题单

上一题 下一题 算法标签: