Let s be a string consisting of lowercase English letters. There exist M restrictions of the form ai bi, (1 ≤ i ≤ M), meaning that letters ai and bi are not allowed to be placed on adjacent positions (two positions are adjacent if their absolute difference is 1).
Your task is to compute the number of permutations of s which respect all M restrictions, and, in addition, are palindromes. Since the answer can be fairly large, you should compute this number modulo 666013.
Note: a permutation is defined by the string associated to it, not by the ordering of indices. For instance, the permutations aba and aba are considered to be the same even if you swap the a's, and should only be counted once.
Input
The first line of input contains the string s.
The second line contains integer M.
Each of the following M lines contains a pair of space separated lowercase English letters.
Output
A single integer: the number of valid palindrome permutations, modulo 666013.
Constraints
- 2 ≤ |s| ≤ 30
- 0 ≤ M ≤ 30
Samples
| Input | Output | Explanation |
|---|---|---|
| aaaabb 0 | 3 | There are 3 palindrome permutations:
|
| abcba 1 b c | 1 | There are 2 palindrome permutations:
|
| dpsidindspdaawiswiunndnuisdiss 1 i n | 499393 | There are actually 1158696000 valid permutations, but we can't count that high. |
First observation: we can work with only half of a palindrome, since there is a bijection between the total number of halves and the total number of palindromes. This reduces our N constraint from 30 to 15.
Second observation: count the frequency of each letter. If more than one letter occurs with an odd frequency, the answer is 0. If exactly one letter occurs with an odd frequency, it must be placed in the middle.
The straight-forward method for generating half of a palindrome is a backtracking algorithm. Since there are at most factorial(15) permutations, this approach times out.
The faster method is based on dynamic programming. Let dp[mask][last] be the number of configurations which:
- use the letters indicated by the positions of 1's in the bitmask
- end with the letter indicated by the position last
This table can be constructed in at least 3 ways:
- Generate future states and solve each of them recursively. This is too slow, since each state can be reached multiple times.
- Generate future states by only taking one step forward, and then solving the newly reached state sometime in the future. This is a bit tricky, because the states have to be solved in a specific order (first, all configurations with 1 positive bit, then all configurations with 2 positive bits, and so on).
- Consider the current state fixed and check what past states it could have been reached from. This approach propagates recursively down to the null configuration, but has the advantage of not having to compute the same state multiple times. Memoization can be used in this regard.
The only aspect we need to address is the fact that identical permutations should only be counted once. Consider, for instance, the permutation aaabbcccccc. Our solution counts the same permutation multiple times, because it rearranges all instances of the letter a (b and c respectively) between them. Thus, we get an answer that is actually factorial(frequency('a')) * factorial(frequency('b')) * factorial(frequency('c')) times larger.
This can be solved by either using a larger data type (such as long long, which is enough for factorial(15)), or by computing the modular multiplicative inverse of these factorials, modulo 666013.
The worst-case complexity is O(2N/2 * N/2).
1 #!/usr/bin/python3 2 from string import ascii_lowercase as alphabet 3 from collections import defaultdict 4 from sys import setrecursionlimit 5 6 setrecursionlimit(10**8) 7 8 mod = 666013 9 10 s = input() 11 m = int(input()) 12 13 bad = defaultdict(lambda: False) 14 solved = defaultdict(lambda: False) 15 dp = defaultdict(lambda: 0) 16 17 stock = "" 18 odd_freqs = 0 19 mid = None 20 21 def solve(conf, last): 22 if solved[(conf, last)]: 23 return dp[(conf, last)] 24 solved[(conf, last)] = True 25 26 for i, x in enumerate(stock): 27 if (conf & (1<<i)) and i != last and not bad[(stock[last], x)]: 28 dp[(conf, last)] += solve(conf - (1<<last), i) 29 30 return dp[(conf, last)] 31 32 def main(): 33 global stock, odd_freqs, mid 34 35 for i in range(m): 36 a, b = input().split() 37 bad[(a, b)] = bad[(b, a)] = True 38 39 odd_freqs = [x for x in alphabet if s.count(x) % 2 == 1] 40 stock = ''.join([x * (s.count(x) // 2) for x in alphabet]) 41 mid = odd_freqs[0] if len(odd_freqs) > 0 else None 42 43 if len(odd_freqs) > 1: 44 print("0") 45 exit(0) 46 47 for i in range(len(stock)): 48 solved[(2**i, i)] = True 49 dp[(2**i, i)] = 1 50 51 sol = 0 52 for i, x in enumerate(stock): 53 if (mid is None and not bad[(x, x)]) or \ 54 (mid is not None and not bad[(x, mid)]): 55 sol += solve(2**(len(stock))-1, i) 56 57 fact = [1] 58 for i in range(1, 20): 59 fact.append(fact[-1] * i) 60 61 for x in alphabet: 62 sol //= fact[stock.count(x)] 63 64 print(sol % mod) 65 66 if __name__ == '__main__': 67 main()
