自动搬运

查看原文

来自洛谷，原作者为

	5ab_juruo May you find some comfort here

搬运于2025-08-24 22:50:43，当前版本为作者最后更新于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;
}