問題一覧 > 通常問題

No.1956 猫の額

レベル : / 実行時間制限 : 1ケース 10.000秒 / メモリ制限 : 15 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 10
作問者 : testestesttestestest / テスター : 37zigen37zigen
1 ProblemId : 4988 / 自分の提出
問題文最終更新日: 2022-05-23 04:45:44

Note

TLとMLの制約にご注意ください。
一部の(多数の?)言語ではAC不能かもしれません。
writer解はC++(ACL利用)で2600ms、Cで適当に書いて9200ms、tester解はC++(ACL不使用)で6200msです。
参考:配列のサイズと型を入力すると何MBか教えてくれるうし

問題文

$N$ 個の正整数 $A_1,\ldots,A_N$ と正整数 $M,C$ が与えられます。$s=1,2,\ldots,\sum_{i=1}^{N}A_i$ のそれぞれについて次の問題に答えてください。

$A_1,\ldots,A_N$ から $C$ 個選んで和を $s$ にする方法は何通りあるか、$\bmod M$ で求めてください。
より厳密には、$|\{I\subset \{1,\ldots,N\} \mid |I|=C \land \sum_{i\in I}A_i=s\}| \bmod M$ を求めてください。

入力

$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$
入力は全て整数

出力

各 $s=1,2,\ldots,\sum_{i=1}^{N}A_i$ に対する答えを、この順に空白区切りで出力せよ。

サンプル

サンプル1
入力
4 10 2
4 3 2 1
出力
0 0 1 1 2 1 1 0 0 0

例えば、
$s=3$ に対しては添字集合として $\{3,4\}$ が
$s=4$ に対しては添字集合として $\{2,4\}$ が
$s=5$ に対しては添字集合として $\{1,4\},\{2,3\}$ が条件を満たします。

サンプル2
入力
10 4 5
1 1 1 1 1 1 1 1 1 1
出力
0 0 0 0 0 0 0 0 0 0

$\bmod M$ で求めてください。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。