Honestly, I'm doing a practice and get blocked. Problem link.
The problem is simple, given a string, calculate the number of max length palindromes (Any substring is valid, which means you can take any chars you want and reorder them as you want). Return the result modulo 1000000007.
For example, given
amim, the answer is
#!/bin/python3 import math import os import random import re import sys from itertools import permutations from functools import lru_cache # Complete the initialize function below. def initialize(s): # This function is called once before all queries. s = [ord(i) - 97 for i in s] results = [ * 26] for i, v in enumerate(s): result = results[i].copy() result[v] += 1 results.append(result) return results def count(s): result =  * 26 for i in s: result[i] += 1 return result factorial = lru_cache(None)(math.factorial) p = 1000000007 pow = lru_cache(None)(pow) # Complete the answerQuery function below. def answerQuery(l, r): # Return the answer for this query modulo 1000000007. counted1 = counted_list[l - 1] counted2 = counted_list[r] counted = [counted2[i] - counted1[i] for i in range(26)] left = 0 total = 0 divide =  for temp in counted: left += temp & 1 total += temp >> 1 divide.append(temp >> 1) total = factorial(total) total = total % p for i in divide: temp = factorial(i) temp = pow(temp, p - 2, p) total = total * temp result = total * (left or 1) return result % p if __name__ == '__main__': s = input() counted_list = initialize(s) q = int(input()) for q_itr in range(q): lr = input().split() l = int(lr) r = int(lr) result = answerQuery(l, r) print(result)
The code above can pass #0~#21 testcases and will fail in #22 due to timeout. (Just copy it to Problem link page given at the top)
As #22 testcase is very huge, I cannot post it here. So here is the link:
If I can use numpy to rewrite this function, I think it will be better. But I cannot, I can only use the standard libs.
I use another customized
factorial function but exceed memory usage limitation :/ But it really reduces the total time cost.
factorial_table = [1, 1] def factorial(n): if n < len(factorial_table): return factorial_table[n] last = len(factorial_table) - 1 total = factorial_table[last] for i in range(last + 1, n + 1): total *= i factorial_table.append(total) return total