当前位置：首页 > news >正文

组合计数 + 拓扑序计数问题

news 2026/6/1 9:45:50

题目描述

问题分析

一、核心规则

二、关键结论

三、解题思路

拓展：逆元是什么？

题目描述

问题分析

一、核心规则

操作只有两种：INSERT id和DELETE id。
合法执行顺序的要求：
- INSERT id必须在DELETE id之前执行（因为插入后才能删除）。
- 初始执行顺序是合法的，且同一id只会出现一次INSERT和一次DELETE（或者只出现INSERT）。
- 调整顺序后，最终数据库状态要和原顺序执行后的结果一致：
- 最终状态里，存在的id是那些只执行了INSERT、没有执行DELETE的记录。
- 被删除的id必须执行过INSERT和DELETE，且INSERT在前。

二、关键结论

对于每个id：
- 如果它有INSERT和DELETE：这两条操作必须满足INSERT在DELETE之前，是一个固定的先后约束。
- 如果它只有INSERT：这条操作没有后续约束，只要不违反其他id的约束即可。
- 如果它只有DELETE：题目保证原顺序合法，这种情况不存在（因为DELETE时必须存在该id，说明前面一定有INSERT）。
所有合法顺序，就是满足所有INSERT(id) → DELETE(id)约束的拓扑序数量。

三、解题思路

预处理操作：
- 记录每个id的INSERT和DELETE操作是否存在。
- 把所有操作分为两类：
  - 成对操作：(INSERT, DELETE)，共k对。
  - 单条操作：仅INSERT，共m条。
- 总操作数n = 2*k + m。
计数公式推导：
- 我们先把n个操作全排列，有n!种方式。
- 对于每一对(INSERT, DELETE)，其中INSERT在DELETE前的情况，只占所有排列的一半（每对的两种顺序中只有一种合法）。
- 因此，总合法顺序数为： \(\text{ans} = \frac{n!}{2^k}\) 其中k是INSERT和DELETE成对的数量。
实现要点：
- 因为结果可能很大，通常题目会要求对1e9+7取模，我们用预处理阶乘 + 快速幂求逆元来计算。
- 2^k的逆元可以用pow(2, k, MOD)的逆元计算。

Java 代码实现

import java.util.*; public class Main { static final int MOD = 1000000007; static final int MAX = 200010; // 假设 N 最大为 2e5 static long[] fact = new long[MAX]; // 快速幂 static long qpow(long a, long b) { long res = 1; while (b > 0) { if ((b & 1) == 1) { res = res * a % MOD; } a = a * a % MOD; b >>= 1; } return res; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); sc.nextLine(); // 预处理阶乘,fact[i] 存储 i! % MOD，方便后续直接取用 fact[0] = 1; for (int i = 1; i <= N; i++) { fact[i] = fact[i - 1] * i % MOD; } Map<Integer, Boolean> hasInsert = new HashMap<>(); Map<Integer, Boolean> hasDelete = new HashMap<>(); for (int i = 0; i < N; i++) { String line = sc.nextLine(); String[] parts = line.split(" "); if (parts[0].equals("INSERT")) { int id = Integer.parseInt(parts[1]); hasInsert.put(id, true); } else if (parts[0].equals("DELETE")) { int id = Integer.parseInt(parts[1]); hasDelete.put(id, true); } } // 统计成对的数量 k:遍历所有 INSERT 的 id，如果该 id 同时有 DELETE，则 k++ int k = 0; for (int id : hasInsert.keySet()) { if (hasDelete.containsKey(id)) { k++; } } // 计算 n! / (2^k) mod MOD long numerator = fact[N]; long denominator = qpow(2, k); long invDenominator = qpow(denominator, MOD - 2); // 费马小定理求逆元 long ans = numerator * invDenominator % MOD; System.out.println(ans); } }