5ab_87 Electro Master

5ab_juruo · 2023-09-29 12:38:46 · 题解

感觉是一个，比较套路的题目？

根据经典结论，向左的粒子个数等于正粒子个数，相邻两个粒子的碰撞次数等于缝隙左侧的负粒子个数。你可以直接 dp 了，但感觉不如算贡献。

枚举 i-1,i,i+1 粒子的正负性，若 i 对答案有贡献，则要求满足以下条件：

• 正粒子至少要有 i 个；
• 左右有效碰撞次数为奇数。

可以进一步分类讨论。若左右粒子正负性相同，则发现当且仅当 +-+ 情况一定有贡献（左右碰撞一定为奇数次），否则就一定没有贡献。对于两侧不同的情况，枚举左侧正粒子的个数（要满足某个奇偶性），乘上后面选 + 可能的情况即可。

要特判开头和 n=1 的情况，不用判结尾是因为一定不会产生贡献。或者在开头加一个 + 避免这部分讨论。

预处理组合数后缀和可做到 O(n^2)。

const int max_n = 2e3 + 1, mod = 998244353;
using mint = mod_int<mod>;

mint sm[max_n + 1][max_n + 1];
int qc[max_n + 1], pc[max_n + 1], nc[max_n + 1];

const vector<int> S[3] = { {0}, {1}, {0, 1} };
inline const vector<int>& P(int x) { return x == '+' ? S[0] : (x == '-' ? S[1] : S[2]); }

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    string s;

    cin >> s;
    s = "+" + s;
    n = ssz(s);

    initfac(n);
    for (int i = 0; i <= n; i++)
    {
        for (int j = 0; j <= i; j++)
            sm[i][j] = C(i, j);
        for (int j = i; j > 0; j--)
            sm[i][j - 1] += sm[i][j];
    }
    for (int i = 0; i < n; i++)
    {
        qc[i + 1] = qc[i] + (s[i] == '?');
        pc[i + 1] = pc[i] + (s[i] == '+');
        nc[i + 1] = nc[i] + (s[i] == '-');
    }

    mint ans = 0;
    for (int i = 1; i < n - 1; i++)
        for (int pr : P(s[i - 1]))
            for (int c : P(s[i]))
                for (int nx : P(s[i + 1]))
                {
                    if (pr == nx)
                    {
                        if (pr == 0 && c == 1)
                            ans += sm[qc[n] - qc[i + 2] + qc[i - 1]][max(0, i + 1 - (pc[n] - pc[i + 2] + pc[i - 1] + 2))];
                        continue;
                    }
                    int odd = (pr == 0 || c == 1) ^ (nc[i - 1] & 1), dv = (c == 0) + 1;
                    for (int j = odd; j <= qc[i - 1]; j += 2)
                        ans += C(qc[i - 1], j) * sm[qc[n] - qc[i + 2]][max(0, i + 1 - (qc[i - 1] - j + pc[i - 1] + dv + pc[n] - pc[i + 2]))];
                }
    cout << ans << endl;

    return 0;
}