r636. P2. 魔法拼圖的排列數 - 高中生程式解題系統

內容

古老魔法工坊有 n 個不同顏色的魔法方塊，每種方塊 c_i 塊可用（數量限制）。工匠要用這些方塊排成長度為 L 的一列（序列位置有區分），每個位置放一塊。問有多少種不同排法（同種顏色方塊視為相同的物件），答案需對模數 M 取餘。數量可能很大，請幫工匠計算。

給 n（顏色數）、每種顏色可用數量 c1..cn，還有目標長度 L 與模數 M。計算用這些方塊組成長度恰好 L 的序列數量（排列，位置不同算不同），每種顏色不能超過其數量 ci。輸出答案 mod M。

輸入說明

n L M
c1 c2 ... cn

1 ≤ n ≤ 200
0 ≤ ci ≤ 10^5
0 ≤ L ≤ 10^5
2 ≤ M ≤ 10^9+7（不一定質數）

輸出說明

單一行：答案（0..M-1）

範例輸入 #1

5 100 10007
200 200 200 200 200

範例輸出 #1

測資資訊：

記憶體限制： 512 MB
不公開測資點#0 (3%): 1.0s , <1K
不公開測資點#1 (3%): 1.0s , <1K
不公開測資點#2 (3%): 1.0s , <1K
不公開測資點#3 (3%): 1.0s , <1K
不公開測資點#4 (3%): 1.0s , <1K
不公開測資點#5 (3%): 1.0s , <1K
不公開測資點#6 (3%): 1.0s , <1K
不公開測資點#7 (3%): 1.0s , <1K
不公開測資點#8 (3%): 1.0s , <1K
不公開測資點#9 (3%): 1.0s , <1K
不公開測資點#10 (7%): 3.0s , <1M
不公開測資點#11 (7%): 3.0s , <1K
不公開測資點#12 (7%): 3.0s , <1K
不公開測資點#13 (7%): 3.0s , <1K
不公開測資點#14 (7%): 3.0s , <1K
不公開測資點#15 (7%): 3.0s , <1K
不公開測資點#16 (7%): 3.0s , <1K
不公開測資點#17 (7%): 3.0s , <1M
不公開測資點#18 (7%): 3.0s , <1K
不公開測資點#19 (7%): 3.0s , <1K

提示：

(30%) L ≤ 2000, n ≤ 50。
(70%) 原題範圍

標籤:

Algorithm Challenge contest Zaim

出處:

[管理者：

chenwei98050 ... (陳維（Z）) ]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」