企业官网建设流程全解析

目录

题目描述

问题分析

一、核心规则

二、关键结论

三、解题思路

拓展：逆元是什么？

题目描述

问题分析

一、核心规则

1. 操作只有两种：INSERT id和DELETE id。
2. 合法执行顺序的要求：
   • 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)约束的拓扑序数量。

三、解题思路

1. 预处理操作：

   • 记录每个id的INSERT和DELETE操作是否存在。
   • 把所有操作分为两类：
     • 成对操作：(INSERT, DELETE)，共k对。
     • 单条操作：仅INSERT，共m条。
   • 总操作数n = 2*k + m。

2. 计数公式推导：

   • 我们先把n个操作全排列，有n!种方式。
   • 对于每一对(INSERT, DELETE)，其中INSERT在DELETE前的情况，只占所有排列的一半（每对的两种顺序中只有一种合法）。
   • 因此，总合法顺序数为： \(\text{ans} = \frac{n!}{2^k}\) 其中k是INSERT和DELETE成对的数量。

3. 实现要点：

   • 因为结果可能很大，通常题目会要求对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); } }

拓展：逆元是什么？

逆元就是在模运算里把除法变成乘法，从而避免除法带来的问题（比如溢出、无法整除）。

在模运算里，我们没法直接做除法。 比如：

• 正常数学里，a ÷ b = a × (1/b)
• 但在模运算里，1/b这个分数不存在，我们需要找一个整数inv(b)，让它满足：
• 这个inv(b)，就叫做b在模MOD下的乘法逆元。

有了逆元，除法就可以转换成乘法：

逆元怎么求？（费马小定理）

当MOD是一个质数（比如题目里的1e9+7），且b(要除的那个数) 和MOD互质时，我们可以用费马小定理快速求逆元：

总结

• 逆元的本质：模运算里的 “倒数”，让除法变成乘法。
• 核心作用：
  1. 解决模运算中无法直接做除法的问题
  2. 避免大数除法导致的溢出和计算错误
• 使用前提：模数MOD是质数，且除数b和MOD互质（题目里的2和1e9+7就满足）。