No.1956 Cat's Forehead
タグ : / 解いたユーザー数 12
作問者 :
testestest
/ テスター :
37zigen
Note
Please be careful about the TL and ML constraints.
It may be impossible to get AC in some (many?) languages.
The writer's solution takes 2600ms in C++ (using ACL), 9200ms when written casually in C, and the tester's solution takes 6200ms in C++ (without ACL).
Reference: A cow that tells you how many MB an array takes when you enter its size and type
Problem Statement
You are given $N$ positive integers $A_1,\ldots,A_N$ and positive integers $M,C$. For each of $s=1,2,\ldots,\sum_{i=1}^{N}A_i$, answer the following problem.
Find the number of ways to choose $C$ of $A_1,\ldots,A_N$ so that their sum is $s$, modulo $\bmod M$.
More precisely, find $|\{I\subset \{1,\ldots,N\} \mid |I|=C \land \sum_{i\in I}A_i=s\}| \bmod M$.
Input
$N$ $M$ $C$ $A_1$ $\ldots$ $A_N$
$1\leq N\leq 90$
$2\leq M\leq 10^9$
$1\leq C\leq N$
$1\leq \sum_{i=1}^{N}A_i\leq 10^5$
$1\leq A_i$
All inputs are integers.
Output
Output the answers for $s=1,2,\ldots,\sum_{i=1}^{N}A_i$ in this order, separated by spaces.
Sample
Sample 1
Input
4 10 2 4 3 2 1
Output
0 0 1 1 2 1 1 0 0 0
For example,
for $s=3$, the index set $\{3,4\}$ satisfies the condition,
for $s=4$, the index set $\{2,4\}$ satisfies the condition, and
for $s=5$, the index sets $\{1,4\},\{2,3\}$ satisfy the condition.
Sample 2
Input
10 4 5 1 1 1 1 1 1 1 1 1 1
Output
0 0 0 0 0 0 0 0 0 0
Find the answer in $\bmod M$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。