Ash and his Assignment
All submissions for this problem are available.
Brock likes competitive programming very much. Therefore he decided to take training from Ash, one of the best coaches in India. Ash used to give an assignment to his students every day. He was known for his difficult problems and only the best of his students could solve those problems.
It was Brock's first day in the camp and he wanted to impress his Coach by solving the problem. But after spending 6 hours on the problem, Brock wants help from you.
Help Brock solve the problem which goes as follows.
- You have n dishes and m ingredients given.
- Dishes are numbered from 1 to n.Each ingeredient can be represented as an english lowercase alphabet(a to z).
- Each dish can contain only one ingredient.
- Some of the dishes already contains an ingredient and some of them doesn't which is represented by a '?'.
- Now you have to add any of the m ingrediemts to this unknown dish(unknown dish will be represented by '?'. Multiple dishes may have the same ingredient.
- You are also given Q restrictions of the form (x y) where each restriction reperesents that dish x and dish y should have the same ingredient in it.(1-based index)
- You have to tell the number of ways to add ingredients to unknown dishes so that all the Q restrictions are followed.
- As number of ways can be very large answer it as modulo 1000000007.
- Two ways are considered different if there is at least one dish with different ingredient.
- If it is impossible to satisfy all Q conditions output -1.
First line will contain n and m (number of dishes and number of ingredients).
All the dishes are numbered from 1 to n and ingredients from 1 to m where m<=26
Next line will follow a string representing n dishes where each character will be lowercase english alphabet or a question mark('?').
Next line will contain an integer Q, number of restrictions.
Next Q lines will follow pairs of integers x y.The ingredient in dish x and y should be same.
Output a single line containing number of ways to fill ingredients in unknown dishes satisfying given Q restrictions.
Output your answer by taking modulo with 1000000007. If it is impossible to get such configuration then output -1.
For better understanding look at the explanation given below.
Input: 5 3 ababc 1 1 3 Output: 1
Input: 5 4 ab?b? 1 1 3 Output: 4
Input: 5 3 a?cb? 2 1 3 2 5 Output: -1
Example case 1. The only valid final form is "ababc". So number of ways will be 1.
Example case 2. The valid forms are: "ababa","ababb","ababc","ababd"
Example case 3. No valid configuration can be formed as position 1 and 3 should be same but they are already given some different ingredients
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, 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, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.