Codeforces 1679E DP

传送门 Codeforces 1679E Typical Party in Dorm

枚举子串，考虑到回文串的性质，从字串中间开始枚举。令 ∣ t ∣ = s z lvert trvert = sz ∣t∣=sz。设 a , b a,b a,b 分别为子串中对称位置的字符，若 a = ′ ? ′ , b = ′ ? ′ a='?',b='?' a=′?′,b=′?′，必须设置相同的字符，则贡献为乘以 s z sz sz；若 a = ′ ? ′ a='?' a=′?′ 或 b = ′ ? ′ b='?' b=′?′ 则其对称位置的字符必须包含在查询串 t t t 中才可能为回文串；若 a ≠ ′ ? ′ , b ≠ ′ ? ′ aneq '?', bneq '?' a​=′?′,b​=′?′，则当 a ≠ b aneq b a​=b 时不可能为回文串。所枚举的子串外部的问号可以任意设置字符。

枚举 s z sz sz，问题转换为求解如何快速求解集合所包含的任意子集的贡献，这样的问题可以 O ( s z 2 s z ) O(sz 2^{sz}) O(sz2sz) 求解（传送门）。

总时间复杂度 O ( s z × n 2 + s z 2 2 s z ) O(sz times n^2 + sz^2 2^{sz}) O(sz×n2+sz22sz)。

#include 
using namespace std;
using ll = long long;
constexpr int MOD = 998244353;

void add(int &x, int y)
{
    x += y;
    if (x >= MOD)
        x -= MOD;
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int N;
    string S;
    cin >> N >> S;
    int mx = 17;
    vector> pw(mx + 1, vector(N + 1));
    for (int i = 1; i <= mx; ++i)
    {
        pw[i][0] = 1;
        for (int j = 1; j <= N; ++j)
            pw[i][j] = (ll)pw[i][j - 1] * i % MOD;
    }
    int num = 0;
    for (int i = 0; i < N; ++i)
        num += S[i] == '?';
    vector> dp(mx + 1, vector(1 << mx));
    for (int i = 0; i < N; ++i)
    {
        bool ok = 1;
        int f = 0, g = num;
        int s = 0;
        for (int w = 0; 0 <= i - w && i + w < N; ++w)
        {
            auto a = S[i - w], b = S[i + w];
            if (a == b)
            {
                if (a == '?')
                    ++f, g -= 1 + bool(i - w != i + w);
            }
            else
            {
                if (a == '?')
                    s |= 1 << (b - 'a'), --g;
                else if (b == '?')
                    s |= 1 << (a - 'a'), --g;
                else
                    ok = 0;
            }
            if (ok == 0)
                break;
            for (int sz = 1; sz <= mx; ++sz)
                add(dp[sz][s], pw[sz][f + g]);
        }
    }
    for (int i = 0; i + 1 < N; ++i)
    {
        int l = i, r = i + 1;
        int f = 0, g = num;
        int s = 0;
        bool ok = 1;
        for (int w = 0; 0 <= l - w && r + w < N; ++w)
        {
            auto a = S[l - w], b = S[r + w];
            if (a == b)
            {
                if (a == '?')
                    ++f, g -= 2;
            }
            else
            {
                if (a == '?')
                    --g, s |= 1 << (b - 'a');
                else if (b == '?')
                    --g, s |= 1 << (a - 'a');
                else
                    ok = 0;
            }
            if (ok == 0)
                break;
            for (int sz = 1; sz <= mx; ++sz)
                add(dp[sz][s], pw[sz][f + g]);
        }
    }
    for (int sz = 1; sz <= mx; ++sz)
    {
        for (int i = 0; i < mx; ++i)
            for (int j = 0; j < 1 << mx; ++j)
                if (j >> i & 1)
                    add(dp[sz][j], dp[sz][j ^ 1 << i]);
    }
    int Q;
    cin >> Q;
    while (Q--)
    {
        string t;
        cin >> t;
        int s = 0;
        for (auto c : t)
            s |= 1 << (c - 'a');
        cout << dp[t.size()][s] << 'n';
    }
    return 0;
}