Typical Party in Dorm (Codeforces 1679E)
Tags: DP, combinatorics

Today is a holiday in the residence hall — Oleh arrived, in honor of which the girls gave him a string. Oleh liked the gift a lot, so he immediately thought up and offered you, his best friend, the following problem.You are given a string $$$s$$$ of length $$$n$$$, which consists of the first $$$17$$$ lowercase Latin letters {$$$a$$$, $$$b$$$, $$$c$$$, $$$\ldots$$$, $$$p$$$, $$$q$$$} and question marks. And $$$q$$$ queries. Each query is defined by a set of pairwise distinct lowercase first $$$17$$$ letters of the Latin alphabet, which can be used to replace the question marks in the string $$$s$$$.The answer to the query is the sum of the number of distinct substrings that are palindromes over all strings that can be obtained from the original string $$$s$$$ by replacing question marks with available characters. The answer must be calculated modulo $$$998\,244\,353$$$.Pay attention! Two substrings are different when their start and end positions in the string are different. So, the number of different substrings that are palindromes for the string aba will be $$$4$$$: a, b, a, aba.Consider examples of replacing question marks with letters. For example, from the string aba??ee when querying {$$$a$$$, $$$b$$$} you can get the strings ababaee or abaaaee but you cannot get the strings pizza,  abaee, abacaba, aba?fee, aba47ee, or abatree.Recall that a palindrome is a string that reads the same from left to right as from right to left.

Input: The first line contains a single integer $$$n$$$ ($$$1 \le n \le 1\,000$$$) — the length of the string $$$s$$$.The second line contains the string $$$s$$$, which consists of $$$n$$$ lowercase Latin letters and question marks. It is guaranteed that all letters in the string belong to the set {$$$a$$$, $$$b$$$, $$$c$$$, $$$\ldots$$$, $$$p$$$, $$$q$$$}.The third line contains a single integer $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$) — the number of queries.This is followed by $$$q$$$ lines, each containing a single line $$$t$$$ — a set of characters that can replace question marks ($$$1 \le |t| \le 17$$$). It is guaranteed that all letters in the string belong to the set {$$$a$$$, $$$b$$$, $$$c$$$, $$$\ldots$$$, $$$p$$$, $$$q$$$} and occur at most once.

Output: For each query print one number — the total numbers of palindromic substrings in all strings that can be obtained from the string $$$s$$$, modulo $$$998\,244\,353$$$.

Note: Consider the first example and the first query in it. We can get only one string as a result of replacing the question marks  — abaaaba. It has the following palindrome substrings:   a  — substring [$$$1$$$; $$$1$$$].  b  — substring [$$$2$$$; $$$2$$$].  a  — substring [$$$3$$$; $$$3$$$].  a  — substring [$$$4$$$; $$$4$$$].  a  — substring [$$$5$$$; $$$5$$$].  b  — substring [$$$6$$$; $$$6$$$].  a  — substring [$$$7$$$; $$$7$$$].  aa  — substring [$$$3$$$; $$$4$$$].  aa  — substring [$$$4$$$; $$$5$$$].  aba  — substring [$$$1$$$; $$$3$$$].  aaa  — substring [$$$3$$$; $$$5$$$].  aba  — substring [$$$5$$$; $$$7$$$].  baaab  — substring [$$$2$$$; $$$6$$$].  abaaaba  — substring [$$$1$$$; $$$7$$$]. In the third request, we get 4 lines: abaaaba, abababa, abbaaba, abbbaba.

Sample Inputs:
7
ab??aba
8
a
b
ab
abc
abcd
abcde
abcdef
abcdefg

11
???????????
6
abcdefghijklmnopq
ecpnkhbmlidgfjao
olehfan
codef
glhf
q

Sample Outputs:
14
13
55
105
171
253
351
465

900057460
712815817
839861037
756843750
70840320
66

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def f(u, v):
    return u * m + v
n = int(input())
s = list(input().rstrip())
mod = 998244353
for i in range(n):
    s[i] -= 97
l = 17
pow2 = [1]
for _ in range(l - 1):
    pow2.append(2 * pow2[-1])
m = 2 * pow2[l - 1]
p = [[1] * (l + 1)]
c = s.count(-34)
for _ in range(c + 3):
    la = p[-1]
    p0 = [la[i] * i % mod for i in range(l + 1)]
    p.append(p0)
dp = [0] * (m * (l + 1))
p0 = p[c]
for i in range(1, l + 1):
    u = f(i, 0)
    dp[u] = p0[i] * n % mod
for i in range(n - 1):
    for j in range(1, 3):
        (x, b) = (c, 0)
        (l0, r0) = (i, i + j)
        while 0 <= l0 and r0 < n:
            (sl, sr) = (s[l0], s[r0])
            if sl == sr:
                if sl < 0:
                    x -= 1
            elif sl < 0:
                x -= 1
                b |= pow2[sr]
            elif sr < 0:
                x -= 1
                b |= pow2[sl]
            else:
                break
            p0 = p[x]
            for k in range(1, l + 1):
                u = f(k, b)
                dp[u] += p0[k]
                dp[u] %= mod
            l0 -= 1
            r0 += 1
for i in pow2:
    for j in range(i + m, m * (l + 1)):
        if i & j:
            dp[j] += dp[i ^ j]
            dp[j] %= mod
q = int(input())
ans = []
for _ in range(q):
    t = list(input().rstrip())
    x = 0
    for i in t:
        x ^= pow2[i - 97]
    ans0 = dp[f(len(t), x)]
    ans.append(ans0)
sys.stdout.write('\n'.join(map(str, ans)))

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def f(u, v):
    return u * m + v
n = int(input())
s = list(input().rstrip())
mod = 998244353
for i in range(n):
    s[i] -= 97
l = 17
pow2 = [1]
for _ in range(l - 1):
    pow2.append(2 * pow2[-1])
m = 2 * pow2[l - 1]
p = [[1] * (l + 1)]
c = s.count(-34)
for _ in range(c + 3):
    la = p[-1]
    p0 = [la[i] * i % mod for i in range(l + 1)]
    p.append(p0)
dp = [0] * (m * (l + 1))
p0 = p[c]
for i in range(1, l + 1):
    u = f(i, 0)
    dp[u] = p0[i] * n % mod
for i in range(n - 1):
    for j in range(1, 3):
        (x, b) = (c, 0)
        (l0, r0) = (i, i + j)
        while 0 <= l0 and r0 < n:
            (sl, sr) = (s[l0], s[r0])
            if sl == sr:
                if sl < 0:
                    x -= 1
            elif sl < 0:
                x -= 1
                b |= pow2[sr]
            elif sr < 0:
                x -= 1
                b |= pow2[sl]
            else:
                break
            p0 = p[x]
            for k in range(1, l + 1):
                u = f(k, b)
                dp[u] += p0[k]
            l0 -= 1
            r0 += 1
for i in pow2:
    for j in range(i + m, m * (l + 1)):
        if i & j:
            dp[j] += dp[i ^ j]
            dp[j] %= mod
q = int(input())
ans = []
for _ in range(q):
    t = list(input().rstrip())
    x = 0
    for i in t:
        x ^= pow2[i - 97]
    ans0 = dp[f(len(t), x)] % mod
    ans.append(ans0)
sys.stdout.write('\n'.join(map(str, ans)))

Solution (Python):
from sys import stdin
input = lambda : stdin.readline()[:-1]
n = int(input())
s = [ord(i) - 97 if 'a' <= i <= 'q' else -1 for i in input()]
cumL = [0] * n
for i in range(n - 1):
    cumL[i + 1] = cumL[i] + (s[i] == -1)
cumR = [0] * n
for i in range(n - 1, 0, -1):
    cumR[i - 1] = cumR[i] + (s[i] == -1)
popcnt = [0] * (1 << 17)
for i in range(1, 1 << 17):
    popcnt[i] = popcnt[i >> 1] + (i & 1)
ans = [0] * (1 << 17)
mod = 998244353
for size in range(1, 18):
    POW = [1] * (n + 1)
    for i in range(1, n + 1):
        POW[i] = POW[i - 1] * size % mod
    dp = [0] * (1 << 17)
    for i in range(n):
        for (l, r) in [(i, i), (i, i + 1)]:
            flag = True
            free = 0
            mask = 0
            for _ in range(n):
                if 0 <= l <= r < n:
                    if s[l] == s[r]:
                        if s[l] == -1:
                            free += 1
                    elif s[l] == -1:
                        mask |= 1 << s[r]
                    elif s[r] == -1:
                        mask |= 1 << s[l]
                    else:
                        flag = False
                    if flag:
                        dp[mask] += POW[free + cumL[l] + cumR[r]]
                l -= 1
                r += 1
    for i in range(17):
        for bit in range(1 << 17):
            if bit >> i & 1:
                dp[bit] += dp[bit ^ 1 << i]
            dp[bit] %= mod
    for i in range(1 << 17):
        if popcnt[i] == size:
            ans[i] = dp[i]
for _ in range(int(input())):
    bit = 0
    for i in input():
        bit |= 1 << ord(i) - 97
    print(ans[bit])