202 . 名貴賽馬排列問題

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

abcabcabc

User's AC Ratio

100.0% (1/1)

Submission's AC Ratio

60.0% (3/5)

Tags

ioicamp ioicamp-2021

Description

貴最喜歡賽馬娘了！

其中貴又有 N 個喜歡的賽馬娘排列樣式。

賽馬娘有什麼好排列的呢？你可能會問。

就讓貴來教教你世間的正道吧！

儘管賽馬娘都是母的，不過賽馬娘的前世有公的也有母的，而貴正是能一眼看出賽馬娘前世性別的男人。

對於每種 M 隻賽馬娘的排列，貴都會用他喜歡的 N 個排列樣式來檢驗它。

只有符合其中至少 NPQ 個排列樣式的馬娘排列才能獲得貴的認證。

每個排列樣式都形如一個長度 M 的字串，且每個字元都是 0 、1 或 ? 中的一個。

第 i 個字元是 0代表在這個排列樣式中貴希望第 i 隻賽馬娘的前世性別是公的，

第 i 個字元是 1代表在這個排列樣式中貴希望第 i 隻賽馬娘的前世性別是母的，

第 i 個字元是 ?代表在這個排列樣式中貴對第 i 隻賽馬娘的前世性別沒有限制。

而對於每個排列樣式，只要賽馬娘的排列中有任何一個位置的賽馬娘的前世性別和貴所希望的一樣（必須是字串中不是 ?的位置），貴就會感到滿意並將該排列視為符合排列樣式。

特別的，對於全部字元都是 ?的排列樣式，所有排列都是符合的。

現在，貴想知道所有 M 隻賽馬娘排列對應到她們前世的公母排列中（總共有 2M 種），有幾種是能獲得貴的認證的呢？（符合至少 NPQ 個排列樣式）

請你告訴貴這個問題的答案吧！（你肯定不會讓貴失望的吧？）

Input Format

第一行輸入四個正整數 M,N,P,Q。

接下來 N 行每行輸入一個長度 M 的字串代表一個排列樣式 ：

  • 0 所在的位置代表希望該賽馬娘的前世性別是公的。
  • 1 所在的位置代表希望該賽馬娘的前世性別是母的。
  • ? 則代表無限制。

資料滿足：

  • M≤20,N≤105
  • P≤Q≤100

Output Format

輸出一個整數代表能被貴認證的公母排列數量。

Sample Input 1

5 1 1 2
?01?0

Sample Output 1

28

Sample Input 2

10 19 25 27
000??1??11
??1?1?0??0
00011?110?
10010011??
11?011000?
0???000100
?01001?1?1
1???010??1
0?1?0???0?
01?00?0??1
??1010??01
01110000?0
?0?1??10?0
0?11101?00
1?01?10?01
00111?1?0?
?11?1000?0
11?1?0110?
000??01101

Sample Output 2

992

Hints

範例測資一中，所有滿足第二隻賽馬娘的前世性別是公的或是第三隻賽馬娘的前世性別是母的或是第五隻賽馬娘的前世性別是公的的排列都符合 ?01?0 這個排列樣式，總共有 28 種。

Problem Source

IOICamp 2021 Day2 pB

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~49 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 262144 65536 1 2
1 1000 262144 65536 1 2
2 1000 262144 65536 2
3 1000 262144 65536 2
4 1000 262144 65536 2
5 1000 262144 65536 2
6 1000 262144 65536 2
7 1000 262144 65536 2
8 1000 262144 65536 2
9 1000 262144 65536 2
10 1000 262144 65536 2
11 1000 262144 65536 2
12 1000 262144 65536 2
13 1000 262144 65536 2
14 1000 262144 65536 2
15 1000 262144 65536 2
16 1000 262144 65536 2
17 1000 262144 65536 2
18 1000 262144 65536 2
19 1000 262144 65536 2
20 1000 262144 65536 2
21 1000 262144 65536 2
22 1000 262144 65536 2
23 1000 262144 65536 2
24 1000 262144 65536 2
25 1000 262144 65536 2
26 1000 262144 65536 2
27 1000 262144 65536 2
28 1000 262144 65536 2
29 1000 262144 65536 2
30 1000 262144 65536 2
31 1000 262144 65536 2
32 1000 262144 65536 2
33 1000 262144 65536 2
34 1000 262144 65536 2
35 1000 262144 65536 2
36 1000 262144 65536 2
37 1000 262144 65536 2
38 1000 262144 65536 2
39 1000 262144 65536 2
40 1000 262144 65536 2
41 1000 262144 65536 2
42 1000 262144 65536 2
43 1000 262144 65536 2
44 1000 262144 65536 2
45 1000 262144 65536 2
46 1000 262144 65536 2
47 1000 262144 65536 2
48 1000 262144 65536 2
49 1000 262144 65536 2
Submit
Back to Top