c699: 軍隊部署 2
標籤 : DP
通過比率 : 0% (0 人 / 1 人 ) (非即時)
評分方式:
Tolerant

最近更新 : 2018-08-27 10:58

內容

記得 c460 嗎?

亞歷山大的軍隊勢如破竹、席捲四方,如今帝國霸業蒸蒸日上。

揉合各地的勢力後,軍隊在管理上產生變革,現在總共有 X 個種族和 Y 種特性被挑選出來。

亞歷山大想從 X 個種族中各選擇一個兵種,請你幫忙計算有多少組合能涵蓋所有特性。

輸入說明

第一列為三個正整數 $\color{black}{N \le 300000,\space X \le 7,\space Y \le 20}$,分別代表亞歷山大麾下有多少種兵種、種族和特性。

接下來的 N 列,每一列有 1 + Y 個正整數 $\color{black}{1 \le c_i \le X,\space a_{i_1},...,a_{i_Y} \in \{0, 1\}}$,
彼此間以一個空白隔開,分別代表種族以及 Y 個特性。
$\color{black}{a_{i_j}}$ 的值若為 1,代表具有第 $\color{black}{j}$ 個特性;否則,不具有該特性。

輸出說明

輸出共有多少個兵種組合可以涵蓋所有種族和特性,由於答案可能很大,請輸出對 $\color{black}{10^9+7}$ 取餘數的結果。

範例輸入
範例輸入一:
9 3 3
1 0 0 0
1 1 1 1
2 0 1 1
1 1 0 1
2 0 0 0
3 0 0 0
3 1 0 1
3 0 1 1
2 0 1 1

範例輸入二:
3 3 2
1 0 1
2 0 0
3 1 0
範例輸出
範例輸出一:
18

範例輸出二:
1
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (10%): 0.5s , <1M
公開 測資點#1 (10%): 0.5s , <1M
公開 測資點#2 (10%): 0.5s , <1M
公開 測資點#3 (10%): 0.5s , <1M
公開 測資點#4 (10%): 0.5s , <10M
公開 測資點#5 (10%): 0.5s , <10M
公開 測資點#6 (10%): 0.5s , <10M
公開 測資點#7 (10%): 1.0s , <10M
公開 測資點#8 (10%): 1.0s , <50M
公開 測資點#9 (10%): 1.0s , <50M
提示 :

對於前 30% 測資,N <= 10000, X = Y = 3。

對於前 60% 測資,N <= 100000, X <= 7, Y <= 10。

對於所有測資,N <= 300000, X <= 7, Y <= 20。

標籤:
DP
出處:
[編輯:
icube (不會寫程式)
]


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