企业官网建设流程全解析

3577: 统计计算机解锁顺序排列数

用计算机 j 解锁计算机 i 的前提是 j<i 且 complexity[j]<complexity[i]。

观察：

• 一开始就解锁的只有计算机 0。
• 第一轮，被 0 解锁的计算机（记作集合 A），密码复杂度比 complexity[0] 大。
• 第二轮，被集合 A 中的计算机解锁的计算机（记作集合 B），密码复杂度更大，所以也比 complexity[0] 大。
• 第三轮，被集合 B 中的计算机解锁的计算机（记作集合 C），密码复杂度更大，所以也比 complexity[0] 大。
• 依此类推，所有被解锁的计算机的密码复杂度都要比 complexity[0] 大。

定理：当且仅当计算机 0 右边的所有计算机的密码复杂度都比 complexity[0] 大，才能解锁所有计算机。

证明：

根据定理，如果计算机 0 右边的所有计算机的密码复杂度都比 complexity[0] 大，那么我们可以按照任意顺序解锁这 n−1 台计算机，方案数为 n−1 个不同物品的全排列个数，即(n−1)!

class Solution { public: int countPermutations(vector<int>& complexity) { constexpr int MOD=1'000'000'007; long long ans=1; for(int i=1;i<complexity.size();i++){ if(complexity[i]<=complexity[0]) return 0; ans=ans*i%MOD; } return ans; } };