错解思路求 Hack
查看原帖
错解思路求 Hack
746760
User_Unauthorized楼主2023/7/24 14:21

设 fi,j,k\displaystyle f_{i,j,k} 表示数组前 ii 个元素组成的，长度为 jj，末尾元素为 kk 的合法子序列数量。那么可得

\left[k \text{在原数组中第一次出现}\right] & j = 1 \\ f_{i - 1,j,k} & k \neq a_i \\ \sum\limits_c f_{i - 1, j - 1, c} - f_{i - 1, j, a_i} & k = a_i \end{cases}$$ 设 $\displaystyle dp_{i,k} = \sum\limits_j f_{i,j,k}$，那么 $$dp_{i,k} = \begin{cases} dp_{i - 1,k} & k \neq a_i \\ \sum\limits_{c} dp_{i - 1,c} - dp_{i - 1, k} + f_{i - 1, 1, k} + f_{i, 1, k} & k = a_i \end{cases}$$ 其中 $k = a_i$ 情况的算式推导过程如下 $$\begin{aligned} dp_{i, k} &= \sum\limits_{j = 1}^i f_{i,j,k} \\ &= \sum\limits_{j = 2}^i f_{i,j,k} + f_{i,1,k} \\ &= \sum\limits_{j = 2}^i \left(\sum\limits_c f_{i - 1, j - 1, c} - f_{i - 1, j, a_i}\right) + f_{i,1,k} \\ &= \sum\limits_c dp_{i - 1, c} - \sum\limits_{j = 2}^{i - 1}f_{i - 1, j, k} + f_{i, 1, k} \\ &= \sum\limits_c dp_{i - 1, c} - \left(\sum\limits_{j = 1}^{i - 1}f_{i - 1, j, k} - f_{i - 1, 1, k}\right) + f_{i, 1, k} \\ &= \sum\limits_c dp_{i - 1, c} - dp_{i - 1, k} + f_{i - 1, 1, k} + f_{i, 1, k} \\ \end{aligned}$$ 代码如下： ```cpp //B #include <bits/stdc++.h> typedef long long valueType; typedef std::vector<valueType> ValueVector; typedef std::vector<bool> bitset; constexpr valueType MOD = 998244353; void Inc(valueType &a, valueType b) { b %= MOD; a = (a + b) % MOD; if (a < 0) a += MOD; } class Sum { public: typedef ValueVector container; private: valueType size, _sum_; container data; public: explicit Sum(valueType n) : size(n), _sum_(0), data(n, 0) {}; valueType sum() const { return _sum_; } void set(valueType pos, valueType key) { key %= MOD; Inc(_sum_, key - data[pos]); data[pos] = key; } const valueType &operator()(valueType n) const { return data[n]; } }; int main() { valueType N; std::cin >> N; ValueVector source(N); for (auto &iter: source) std::cin >> iter; ValueVector count(N + 1, 0); bitset exist(N + 1, false); Sum dp(N + 1); for (auto const &iter: source) { valueType const addon = count[iter] + (!exist[iter] ? 1 : 0); dp.set(iter, dp.sum() - dp(iter) + addon); if (!exist[iter]) { exist[iter] = true; count[iter] = 1; } else { count[iter] = 0; } } std::cout << dp.sum() << std::endl; } ``` 如果将这份代码提交，会返回 [WA](https://www.luogu.com.cn/record/117189151) 的结果，请求一份 Hack，谢谢各位大佬。
2023/7/24 14:21