[C++知识库] Codeforces 1679E DP

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> C++知识库 -> Codeforces 1679E DP -> 正文阅读

[C++知识库]Codeforces 1679E DP

题意

传送门 Codeforces 1679E Typical Party in Dorm

题解

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

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

总时间复杂度 $\times n^2 + sz^2 2^{sz})$ 。

#include <bits/stdc++.h>
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<vector<int>> pw(mx + 1, vector<int>(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<vector<int>> dp(mx + 1, vector<int>(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;
}