Chef and Filters
All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Nobody outside the cooking community knows that Chef is a big fan of Chefgram™ — a social network where chefs and cooks upload their secret kitchen photos. Recently Chef clicked a beautiful photo, which is represented using 10 pixels in a single row. Respecting Chefgram™'s boolean roots, every pixel is either white or black.
Chefgram™ has N filters. Every filter is a string containing 10 symbols. Every symbol is either '+' or '-'.
- A '+' at the ith position in a filter means that if Chef applies this filter to his photo, the ith pixel will be inverted: it becomes black if it was originally white, and vice versa.
- A '-' at the ith position in a filter string means that if Chef applies this filter to his photo, the ith pixel will remain unchanged.
Chef can apply as many filters as he wants from a list. He can pick any subset of filters and consequently apply them to a photo.
- Imagine that Chef has a photo "bbwwbbwwbb" (where 'b' stands for black and 'w' stands for white).
- He applies filters "++--++--++", "-+-+-+-+-+".
- Applying the first filter will transform his picture to "wwwwwwwwww".
- Applying the second filter on the transformed picture will give Chef the picture "wbwbwbwbwb".
Even if Chefgram™ has two or more identical filters, they are still considered different!
Chef is extremely interested in knowing how many different subsets of all the Chefgram™ filters can he apply to transform his photo into 10 black pixels?
- The first line of input contains a single integer T — the number of test cases.
- First line of each test case contains a string S. Each symbol is either 'b' or 'w'. This is Chef's photo.
- Second line of each test case contains a single integer N — the number of Chefgram™ filters.
- Each of the next N lines contains a single string Fi, each symbol of which is either '+' or '-'. This string is the ith Chefgram™ filter.
- For each test case, output a single line containing a single integer — answer to Chef's question modulo 109+7.
- 1 ≤ T ≤ 5
- |S| = 10
- 1 ≤ N ≤ 10^5
- |Fi| = 10
- Subtask 1: T ≤ 5; N ≤ 20; Points: 20
- Subtask 2: T ≤ 5; N ≤ 10^3; Points: 30
- Subtask 3: T ≤ 5; N ≤ 10^5; Points: 50
Input: 3 wwwwwwwwww 3 +-+-+-+-+- ---------- +--------- wbwbwbwbwb 3 +-+-+-+-+- +-+------- ----+-+-+- bbbbbbbbbb 2 ---------- ---------- Output: 0 2 4
Example case 1. There is no filter or combination of filters transforming the picture to whole black.
Example case 2. Chef can either apply the first filter (and invert all whites) or apply the second and third filters in any order.
Example case 3. Picture is already fully black, and we have two different identity filters. Chef can either apply the empty subset of filters, the first filter only, the second filter only, or both.
|Tags||berezin, dec15, dynamic-programming, easy|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.