可怜有一个数组 A，定义它的复杂度 c(A) 等于它本质不同的子区间个数。举例来说，c([1,1,1])=3，因为 [1,1,1] 只有 3 个本质不同的子区间 [1]、[1,1] 和 [1,1,1]；而 c([1,2,1])=5，它包含 5 个本质不同的子区间 [1]、[2]、[1,2]、[2,1]、[1,2,1]。
可怜打算出一道和复杂度相关的题目。众所周知，引入随机性往往可以让一个简单的题目脱胎换骨。现在，可怜手上有一个长度为 n 的正整数数组 x 和一个正整数 m。接着，可怜会独立地随机产生 n 个 [1,m] 中的随机整数 yi，并把 xi 修改为 mxi+yi。
显然，一共有 N=mn 种可能的结果数组。现在，可怜想让你求出这 N 个数组的复杂度的和。
输入格式：
第一行给出一个整数 t (1≤t≤5) 表示数据组数。
对于每组数据，第一行输入两个整数 n 和 m (1≤n≤100,1≤m≤109)，第二行是 n 个空格隔开的整数表示数组 x 的初始值 (1≤xi≤109)。
输出格式：
对于每组数据，输出一行一个整数表示答案。答案可能很大，你只需要输出对 998244353 取模后的结果。
输入样例：
4
3 2
1 1 1
3 2
1 2 1
5 2
1 2 1 2 1
10 2
80582987 187267045 80582987 187267045 80582987 187267045 80582987 187267045 80582987 187267045
输出样例：
36
44
404
44616
代码长度限制
16 KB
时间限制
8000 ms
内存限制
256 MB
栈限制
131072 KB
Java实现（30/30）：
import java.io.*; import java.util.*; public class Main { // 模数 static final long MOD = 998244353; public static void main(String[] args) { // 使用快速 I/O InputStream inputStream = System.in; OutputStream outputStream = System.out; InputReader in = new InputReader(inputStream); PrintWriter out = new PrintWriter(outputStream); Solve solver = new Solve(); int t = in.nextInt(); while (t-- > 0) { solver.solve(in, out); } out.close(); } static class Solve { long[] invMPow; public void solve(InputReader in, PrintWriter out) { int n = in.nextInt(); long m = in.nextLong(); // 特判：如果 m 是 MOD 的倍数，结果为 0 (因为 N = m^n % MOD = 0) if (m % MOD == 0) { for (int i = 0; i < n; i++) in.nextInt(); // 消耗输入 out.println(0); return; } int[] x = new int[n]; for (int i = 0; i < n; i++) { x[i] = in.nextInt(); } // 预处理 m 的逆元及其幂次，用于 DP 中快速计算 m^{-covered} long invM = power(m % MOD, MOD - 2); invMPow = new long[n + 1]; invMPow[0] = 1; for (int i = 1; i <= n; i++) { invMPow[i] = (invMPow[i - 1] * invM) % MOD; } // 1. 找出所有本质不同的子区间及其出现位置 // Key: 子区间内容 (List), Value: 出现位置的起始下标列表 (List) Map<List<Integer>, List<Integer>> occurrences = new HashMap<>(); for (int i = 0; i < n; i++) { List<Integer> sub = new ArrayList<>(); for (int j = i; j < n; j++) { sub.add(x[j]); // 注意：必须创建新的 List 作为 Key List<Integer> key = new ArrayList<>(sub); occurrences.computeIfAbsent(key, k -> new ArrayList<>()).add(i); } } long totalAns = 0; long mPowN = power(m % MOD, n); // 2. 对每种本质不同的子区间分别计算贡献 for (Map.Entry<List<Integer>, List<Integer>> entry : occurrences.entrySet()) { List<Integer> sub = entry.getKey(); List<Integer> posList = entry.getValue(); int k = sub.size(); // 子区间长度 int t = posList.size(); // 出现次数 // DP 表：dp[i] 存储以第 i 个出现位置为结尾的所有集合 B 的状态和 // Map Key: 状态 (规范化的并查集数组), Value: long[]{奇数集合系数和, 偶数集合系数和} List<Map<List<Integer>, long[]>> dp = new ArrayList<>(t); for (int i = 0; i < t; i++) dp.add(new HashMap<>()); // 缓存 merge 操作的结果，避免重复计算 // Key: 当前状态, Value: Map<位移, 新状态> Map<List<Integer>, Map<Integer, List<Integer>>> mergeCache = new HashMap<>(); // 初始状态：长度为 k，所有位置互不连通，规范化表示为 [0, 1, ..., k-1] List<Integer> initialState = new ArrayList<>(k); for (int i = 0; i < k; i++) initialState.add(i); // 初始化 DP：每个单独的位置都是一个大小为 1 的集合 B // 贡献权重 m^{-k} (因为覆盖了 k 个未知数) long initFactor = invMPow[k]; for (int i = 0; i < t; i++) { long[] sums = dp.get(i).computeIfAbsent(initialState, key -> new long[2]); sums[0] = (sums[0] + initFactor) % MOD; // 集合大小为 1 (奇数) } // 3. 执行 DP 转移 for (int i = 0; i < t; i++) { Map<List<Integer>, long[]> currentMap = dp.get(i); if (currentMap.isEmpty()) continue; for (Map.Entry<List<Integer>, long[]> stateEntry : currentMap.entrySet()) { List<Integer> currentState = stateEntry.getKey(); long curOdd = stateEntry.getValue()[0]; long curEven = stateEntry.getValue()[1]; if (curOdd == 0 && curEven == 0) continue; for (int j = i + 1; j < t; j++) { int shift = posList.get(j) - posList.get(i); // 计算新增覆盖长度 // 如果 shift >= k，完全不重叠，新增 k // 如果 shift < k，重叠，新增 shift int addedLen = (shift >= k) ? k : shift; long factor = invMPow[addedLen]; // 获取合并后的新状态 List<Integer> nextState; Map<Integer, List<Integer>> stateCache = mergeCache.computeIfAbsent(currentState, key -> new HashMap<>()); if (stateCache.containsKey(shift)) { nextState = stateCache.get(shift); } else { nextState = mergeState(currentState, k, shift); stateCache.put(shift, nextState); } // 转移更新 // 新集合 B' = B U {j} // 大小奇偶性翻转：奇->偶，偶->奇 long[] nextSums = dp.get(j).computeIfAbsent(nextState, key -> new long[2]); nextSums[0] = (nextSums[0] + curEven * factor) % MOD; nextSums[1] = (nextSums[1] + curOdd * factor) % MOD; } } } // 4. 统计该子区间的总贡献 long subAns = 0; for (int i = 0; i < t; i++) { for (Map.Entry<List<Integer>, long[]> stateEntry : dp.get(i).entrySet()) { long[] sums = stateEntry.getValue(); // 容斥系数： (-1)^{|B|-1} // 奇数大小集合贡献 +，偶数大小集合贡献 - long term = (sums[0] - sums[1] + MOD) % MOD; if (term == 0) continue; int comps = countComponents(stateEntry.getKey()); // 最终项 = term * m^n * m^{components} // term 中包含了 m^{-UnionLength} // 实际自由度 = m^{n - UnionLength + components} long weight = (mPowN * power(m % MOD, comps)) % MOD; subAns = (subAns + term * weight) % MOD; } } totalAns = (totalAns + subAns) % MOD; } out.println(totalAns); } // 合并状态逻辑：模拟重叠产生的约束 private List<Integer> mergeState(List<Integer> state, int k, int shift) { // 使用数组模拟并查集 int[] parent = new int[k]; for (int i = 0; i < k; i++) parent[i] = state.get(i); if (shift < k) { // 如果有重叠，则 y[i] 和 y[i+shift] 必须属于同一个等价类 // 注意：这里 i 是相对于第一个区间的偏移 for (int i = 0; i < k - shift; i++) { union(parent, i, i + shift); } } // 重新规范化为 List，作为 Map 的 Key List<Integer> newState = new ArrayList<>(k); for (int i = 0; i < k; i++) { newState.add(find(parent, i)); } return newState; } private int find(int[] p, int x) { if (p[x] == x) return x; return p[x] = find(p, p[x]); } private void union(int[] p, int i, int j) { int rootI = find(p, i); int rootJ = find(p, j); if (rootI != rootJ) { // 总是让较小的索引作为根，保证规范化结果唯一 if (rootI < rootJ) p[rootJ] = rootI; else p[rootI] = rootJ; } } private int countComponents(List<Integer> state) { int c = 0; for (int i = 0; i < state.size(); i++) { if (state.get(i) == i) c++; } return c; } private long power(long base, long exp) { long res = 1; base %= MOD; while (exp > 0) { if ((exp & 1) == 1) res = (res * base) % MOD; base = (base * base) % MOD; exp >>= 1; } return res; } } // 辅助类：快速输入 static class InputReader { public BufferedReader reader; public StringTokenizer tokenizer; public InputReader(InputStream stream) { reader = new BufferedReader(new InputStreamReader(stream), 32768); tokenizer = null; } public String next() { while (tokenizer == null || !tokenizer.hasMoreTokens()) { try { String str = reader.readLine(); if (str == null) return null; tokenizer = new StringTokenizer(str); } catch (IOException e) { throw new RuntimeException(e); } } return tokenizer.nextToken(); } public int nextInt() { return Integer.parseInt(next()); } public long nextLong() { return Long.parseLong(next()); } } }C++（30/30）：
/** * 核心算法说明： * 1. 预处理：枚举 x 的所有子区间，去重，记录每种本质不同子区间的出现位置列表。 * 2. 状态压缩：用 vector<int> 表示长度为 k 的并查集状态（规范化为最小表示法），映射为 int ID。 * 3. 动态规划： * 对于每种长度 k 的子区间类型： * dp[last_idx][state_id] = {sum_odd, sum_even} * last_idx: 上一个加入集合 B 的出现位置下标 * state_id: 当前长度 k 的内部等价类状态 * 值存储的是 m^{-covered_length} 的累加和 (为了方便处理，先乘逆元，最后乘 m^n) * 4. 转移： * 枚举下一个位置 next_idx，计算 shift = pos[next_idx] - pos[last_idx]。 * 合并等价类，计算新覆盖长度，更新状态。 */ #include <iostream> #include <vector> #include <string> #include <map> #include <set> #include <numeric> #include <algorithm> using namespace std; long long N_val, M_val; const int MOD = 998244353; // 快速幂 long long power(long long base, long long exp) { long long res = 1; base %= MOD; while (exp > 0) { if (exp % 2 == 1) res = (res * base) % MOD; base = (base * base) % MOD; exp /= 2; } return res; } long long modInverse(long long n) { return power(n, MOD - 2); } // 并查集状态的规范化表示 vector<int> normalize_dsu(const vector<int>& p) { int k = p.size(); vector<int> mapping(k, -1); vector<int> canonical(k); // 这里的 p 并不一定是根，需要 find 一下，或者假设外部已经做好了 // 为了安全，我们在外部合并时保证 p[i] 是根或者直接指向根 // 但为了作为 map 的 key，我们需要由一种绝对标准的形态 // 重新实现一个内部查找，确保通过 p 能找到绝对根 auto find_root = [&](int node, auto&& self) -> int { if (p[node] == node) return node; return self(p[node], self); // 不做路径压缩修改原数组，只查询 }; for (int i = 0; i < k; ++i) { canonical[i] = find_root(i, find_root); } return canonical; } // 合并状态 // state: 当前的等价类状态 // k: 长度 // shift: 两个区间的距离 // 返回: {新状态, 减少的连通块数量(用于计算自由度变化)} // 注意：自由度变化不完全等于连通块减少，还要考虑新覆盖的区域 // 这里我们只负责返回新状态。外部逻辑处理覆盖长度。 vector<int> merge_state(const vector<int>& state, int k, int shift) { vector<int> p = state; // copy auto find = [&](int x) { while (x != p[x]) { p[x] = p[p[x]]; x = p[x]; } return x; }; auto unite = [&](int x, int y) { int rootX = find(x); int rootY = find(y); if (rootX != rootY) { if (rootX > rootY) swap(rootX, rootY); p[rootY] = rootX; // 小的当爹，保持字典序优势 } }; if (shift < k) { for (int i = 0; i < k - shift; ++i) { unite(i, i + shift); } } // 重新规范化 for(int i=0; i<k; ++i) p[i] = find(i); return p; } // 计算状态中有多少个本质不同的变量 (连通块数量) int count_components(const vector<int>& state) { int cnt = 0; for (int i = 0; i < state.size(); ++i) { if (state[i] == i) cnt++; } return cnt; } void solve() { int n; long long m; if (!(cin >> n >> m)) return; vector<int> x(n); for (int i = 0; i < n; ++i) cin >> x[i]; // 1. 找出所有本质不同的子区间及其出现位置 // Map: vector<int> (subsegment content) -> vector<int> (start positions) map<vector<int>, vector<int>> occurrences; for (int i = 0; i < n; ++i) { vector<int> current_sub; for (int j = i; j < n; ++j) { current_sub.push_back(x[j]); occurrences[current_sub].push_back(i); } } long long total_ans = 0; long long m_pow_n = power(m, n); long long inv_m = modInverse(m); // 预计算 m 的逆元幂，加速 DP vector<long long> inv_m_pow(n + 1); inv_m_pow[0] = 1; for(int i=1; i<=n; ++i) inv_m_pow[i] = (inv_m_pow[i-1] * inv_m) % MOD; // 按长度分组处理，以便共享 memoization // 虽然 n 很小，直接按 distinct subarray 处理也行 // 但为了性能，我们需要缓存 merge 结果 // 状态 ID 映射 map<vector<int>, int> state_to_id; vector<vector<int>> id_to_state; // Merge 缓存: memo[len][state_id][shift] -> new_state_id // 由于 len 变化，我们可以每次处理一个 distinct subarray 时清空或局部使用 // 鉴于 n=100，总状态数不多，我们可以对每个 subarray 单独跑 for (auto const& [sub, pos_list] : occurrences) { int k = sub.size(); int t = pos_list.size(); // 清空状态映射，针对当前 k state_to_id.clear(); id_to_state.clear(); map<pair<int, int>, int> merge_cache; // 初始状态：完全不连通 {{0},{1},...} vector<int> initial_vec(k); iota(initial_vec.begin(), initial_vec.end(), 0); state_to_id[initial_vec] = 0; id_to_state.push_back(initial_vec); // DP: dp[last_idx][state_id] = {odd_sum, even_sum} // 使用 map 以节省空间，因为稀疏 // key: state_id, val: pair<long long, long long> vector<map<int, pair<long long, long long>>> dp(t); // 辅助函数：获取状态 ID auto get_id = [&](const vector<int>& s) { if (state_to_id.count(s)) return state_to_id[s]; int id = state_to_id.size(); state_to_id[s] = id; id_to_state.push_back(s); return id; }; // 辅助函数：执行 merge 并获取 ID auto perform_merge = [&](int s_id, int shift) { if (merge_cache.count({s_id, shift})) return merge_cache[{s_id, shift}]; vector<int> next_vec = merge_state(id_to_state[s_id], k, shift); int next_id = get_id(next_vec); return merge_cache[{s_id, shift}] = next_id; }; // 初始化 DP // 每一个单独的位置都是一个起始集合 B={pos_list[i]} // 初始贡献：m^{-k} (因为覆盖了 k 个位置，所以概率是 1/m^k，或者说自由度减少 k) // 我们计算 sum (m^{-UnionLength})，最后乘 m^n * m^{components} long long init_factor = inv_m_pow[k]; for (int i = 0; i < t; ++i) { // odd sum 增加, even sum 不变 dp[i][0].first = (dp[i][0].first + init_factor) % MOD; } // DP 转移 for (int i = 0; i < t; ++i) { if (dp[i].empty()) continue; for (auto const& [s_id, sums] : dp[i]) { long long cur_odd = sums.first; long long cur_even = sums.second; if (cur_odd == 0 && cur_even == 0) continue; for (int j = i + 1; j < t; ++j) { int shift = pos_list[j] - pos_list[i]; // 计算新增覆盖长度 // 之前的 union 覆盖了某长度，现在加了一个 [pos_j, pos_j + k) // 新增长度 = k - max(0, k - shift) // 如果 shift >= k，新增 k // 如果 shift < k，新增 shift int added_len = (shift >= k) ? k : shift; long long factor = inv_m_pow[added_len]; int next_s_id = perform_merge(s_id, shift); // 转移： // B_new = B_old U {j} // size parity flips: odd -> even, even -> odd // new_odd += old_even * factor // new_even += old_odd * factor auto& next_entry = dp[j][next_s_id]; next_entry.first = (next_entry.first + cur_even * factor) % MOD; next_entry.second = (next_entry.second + cur_odd * factor) % MOD; } } } // 统计答案 long long sub_ans = 0; for (int i = 0; i < t; ++i) { for (auto const& [s_id, sums] : dp[i]) { long long term = (sums.first - sums.second + MOD) % MOD; if (term == 0) continue; int comps = count_components(id_to_state[s_id]); // 贡献 = term * m^{n + comps} // 注意：term 里面包含了 m^{-UnionLength} // 真正的自由度 = m^{n - UnionLength + comps} // 所以我们只需要乘 m^{n + comps} long long weight = (m_pow_n * power(m, comps)) % MOD; sub_ans = (sub_ans + term * weight) % MOD; } } total_ans = (total_ans + sub_ans) % MOD; } cout << total_ans << endl; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int t; if (cin >> t) { while (t--) { solve(); } } return 0; })
)
