トヨタシステムズプログラミングコンテスト2022(AtCoder Beginner Contest 279)
翻译中…
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.
翻译中…
样例
Input #1
3 5
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$.
Input #2
1126 2022
Output #2
40166
Print the sum modulo $200\ 003$.
Input #3
1000000000000 1500000000000
Output #3
180030
题目信息
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（CI 管线），如有出入请以原文为准。