問題一覧 > 通常問題

No.1474 かさまＪ

レベル : / 実行時間制限 : 1ケース 2.500秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 69
作問者 : gorugo30 / テスター : 37zigen nok0
6 ProblemId : 5960 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-04-04 08:22:34

問題文

かぞえさんは N 人に合計 MP 個の「P」を配ろうと思っていました。
しかし、MP 個の「P」だけでは物足りないと感じ、「q」を Mq 個用意し、同時に配ることにしました。
かぞえさんの目標は、「q」が混じっていることに誰にも気付かれないことです。

N 人は人 1、人 2、…、人 N と呼ばれます。
人 i には、次のような場合に、「q」が混じっていることに気付かれます。

  • 人 i に「q」を Si 個よりも多く配った場合
  • 人 i に「P」と「q」を配った数の合計が L 個未満で、「q」を 1 個以上配った場合
ただし Si<L であり、人 i に「q」を L 個以上配ると必ず気付かれます。

かぞえさんの目標を達成する、MP 個の「P」と、0 個以上 Mq 個以下の「q」の配り方は何通りあるでしょう？

配り方が異なるとは、ある人が存在し、その人に配る「P」の個数と「q」の個数の少なくとも一方が異なることをいいます。
答えを 109+7 で割った余りを出力してください。「P」と「q」を配られた個数がどちらも 0 個であるという人が居るような配り方をしても構いません。

入力

N MP Mq L
S1 S2 … SN

  • 1≤N≤40
  • 1≤MP≤20000
  • 0≤Mq≤20000
  • 1≤L≤10000
  • 0≤Si<L
  • 入力はすべて整数である

出力

最後に改行してください。

サンプル

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

3 個の「P」を 2 人に配る方法は 4 通りあります。

サンプル2
入力
2 2 1 2
1 1
出力
7

この例では、Si の値が Mq 以上なので、Si よりも「q」を配った数が多いという理由で気付かれることはありません。
しかし、ある人に「P」を配らずに「q」1 個だけを配ると、「P」と「q」を配った数は合計 1 個で、L よりも少ないので、気付かれてしまいます。

具体的には、人 i に「P」を配る個数を Xi、「q」を配る個数を Yi として、
((X1,Y1),(X2,Y2))=((0,0),(2,0)) と ((2,0),(0,0)) と ((1,0),(1,0)) と ((0,0),(2,1)) と ((2,1),(0,0)) と ((1,1),(1,0)) と ((1,0),(1,1)) の 7 通りです。

サンプル3
入力
10 1000 500 300
3 141 59 26 53 58 9 79 3 238
出力
595400382

サンプル4
入力
40 20000 20000 10000
2157 1034 6876 6167 5896 500 3354 8114 1607 3534 1655 9796 7967 2942 2745 2401 3813 4770 6036 4858 2479 3793 2714 2029 9078 6633 9111 1285 6800 4795 2241 6173 6797 184 6243 3366 470 6136 2187 8257
出力
590015951

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