题目概述

给定一个多重集的排列，要求计算这个排列在字典序中的排名（从1开始），结果对 $m$ 取模。

例如：多重集 $\{1,1,2,3,3,3,7,8\}$ 有很多种排列，需要计算给定排列的字典序排名。

---

问题分析

关键点

• 这是可重集的排列，不是全排列
• 需要计算在字典序中比给定排列小的排列个数
• $n \leq 300,000$，需要高效算法
• 结果要对 $m$ 取模，$m$ 不一定是质数

字典序排名计算原理

对于排列 $a_1, a_2, \dots, a_n$，其排名 = 所有比它小的排列数量 + 1

比它小的排列可以分为：

• 第一位比 $a_1$ 小的
• 第一位等于 $a_1$，但第二位比 $a_2$ 小的
• 前两位相等，但第三位比 $a_3$ 小的
• ...

---

算法思路

核心公式

对于位置 $i$，设：

• $k$ = 在剩余元素中比 $a_i$ 小的元素个数
• $cnt$ = $a_i$ 在剩余元素中出现的次数
• 剩余元素总数 = $n-i$

那么以 $a_1, a_2, \dots, a_{i-1}$ 为前缀，第 $i$ 位比 $a_i$ 小的排列数量为：

$$\text{count} = k \times \frac{(n-i)!}{\prod (\text{各元素出现次数的阶乘})} $$

从右向左处理

为了高效计算，我们从右向左处理：

1. 维护当前剩余元素的频数
2. 使用树状数组快速查询比当前元素小的元素个数
3. 使用模运算处理大数除法

处理模数 $m$ 不是质数的情况

由于 $m$ 不一定是质数，不能直接使用逆元。解决方案：

• 对 $m$ 进行质因数分解
• 将每个数表示为 $m$ 的质因子的幂次形式
• 在质因子表示下进行乘除法

---

算法详解

数据结构设计

树状数组 (BIT)

用于维护当前剩余元素的分布，支持：

• 添加元素
• 查询比某值小的元素个数

struct BIT {
    int tr[N], siz;
    void add(int x, int k) {
        for (int i = x; i <= siz; i += lowbit(i))
            tr[i] += k;
    }
    int qry(int x) {
        int ret = 0;
        for (int i = x; i; i -= lowbit(i))
            ret += tr[i];
        return ret;
    }
} tr;

有理数表示 (rational)

由于要处理除法且模数不一定是质数，使用质因子表示法：

struct rational {
    ll num[15];  // num[0] 存储与m互质的部分，num[1..cnt]存储各质因子的指数
    void update(ll up, ll down) {
        // 处理up/down，更新质因子指数
        for (int i = 1; i <= cnt; ++i) {
            // 分解up和down的质因子
            // 更新num[i] += (up中bse[i]的指数) - (down中bse[i]的指数)
        }
        // 更新互质部分
        num[0] = num[0] * (up去掉质因子) * inv(down去掉质因子) % p;
    }
    ll to_llong() {
        // 将质因子表示转换为实际数值模p
        ll ret = num[0];
        for (int i = 1; i <= cnt; ++i) {
            ret = ret * qpow(bse[i], num[i]) % p;
        }
        return ret;
    }
} f;

主算法流程

// 初始化：分解模数m的质因子
init();

// 从右向左处理
for (int i = n; i >= 1; --i) {
    tr.add(a[i], 1);  // 将当前元素加入树状数组
    
    if (i < n) {
        ll k = tr.qry(a[i] - 1);        // 比a[i]小的元素个数
        ll cntnum = tr.qry(a[i]) - k;   // a[i]出现的次数
        
        // 更新组合数：乘以(n-i)!，除以各元素出现次数的阶乘
        f.update(n - i, cntnum);
        
        if (k != 0) {
            // 计算以当前前缀 + 更小元素 开头的排列数
            f.update(k, 1);
            ans = (ans + f.to_llong()) % p;
            f.update(1, k);  // 回退
        }
    }
}

// 最终结果要+1（当前排列本身）
cout << (ans + 1) % p;

---

样例解析

样例输入

4 1000
2 1 10 2

多重集：$\{1,2,2,10\}$，给定排列：$(2,1,10,2)$

计算过程

从右向左处理：

1. 处理第3位 (10)：

   • 剩余元素：$\{1,2,2\}$
   • 比10小的元素：$\{1,2,2\}$，共3个
   • 贡献：$3 \times \frac{1!}{1! \cdot 2!} = 0$（因为10是最大元素）

2. 处理第2位 (1)：

   • 剩余元素：$\{2,2,10\}$
   • 比1小的元素：0个
   • 无贡献

3. 处理第1位 (2)：

   • 剩余元素：$\{1,2,10\}$
   • 比2小的元素：$\{1\}$，共1个
   • 贡献：$1 \times \frac{3!}{1! \cdot 1! \cdot 1!} = 6$，但实际要考虑重复...

实际计算得到比给定排列小的排列有4个：

• (1,2,2,10)
• (1,2,10,2)
• (1,10,2,2)
• (2,1,2,10)

所以排名 = 4 + 1 = 5

---

复杂度分析

• 质因数分解：$O(\sqrt{m})$，$m \leq 10^9$
• 树状数组操作：$O(n \log n)$
• 有理数更新：每次 $O(\text{质因子个数})$，质因子个数 ≤ 10
• 总复杂度：$O(n \log n)$

对于 $n \leq 300,000$ 可以接受。

---

算法亮点

1. 逆向处理：从右向左，便于维护剩余元素
2. 树状数组：高效查询比当前元素小的个数
3. 质因子表示：解决非质数模数下的除法问题
4. 组合计数：正确处理可重集排列的计数公式

---

总结

这道题综合了多个重要技巧：

1. 字典序排名算法：经典的可重集排列排名计算
2. 数据结构优化：使用树状数组维护元素分布
3. 模运算处理：针对非质数模数的特殊处理
4. 质因数分解：将数表示为质因子幂次形式

这种"组合计数 + 数论 + 数据结构"的综合性问题在编程竞赛中很常见，需要熟练掌握各个基础组件并能灵活组合运用。