我真零基础啊
由于数组大多数都以 AAA 命名，所以排列数以形如 (nm)m!{n\choose m}m!(mn )m! 表示。
置顶立马删帖。
P6146
Difficulty：3.2 / Easy
这题我怎么都做这么吃力啊。
拆成上半部分和下半部分。
注意到上半部分所有放 iii 个的情况等价。所以考虑枚举 iii。
上半部分的情况数是 (ai)(bi)i!{a\choose i}{b\choose i}i!(ia )(ib )i!，下半部分情况数是 (a+c−ik−i)(d−ik−i)(k−i)!{a+c-i\choose k-i}{d-i\choose k-i}(k-i)!(k−ia+c−i )(k−id−i )(k−i)!，乘起来即可。
时间复杂度：O(k)O(k)O(k)。
P16256
场切，爽！
Difficulty: 4.0 / Easy+
考虑每一个 iii 的贡献。注意到这个贡献是独立的，不受前面（除 i−1i-1i−1）贡献情况的影响。因此可以单独计算。
定义 pre(Ai)\text{pre}(A_i)pre(Ai ) 为 maxj=1iAj\max_{j=1}^i A_jmaxj=1i Aj ，显然如果满足 pre(Bi−1)≤pre(Ai−1),pre(Bi)>pre(Ai)\text{pre}(B_{i-1})\le \text{pre}(A_{i-1}),\text{pre}(B_i)\gt \text{pre}(A_i)pre(Bi−1 )≤pre(Ai−1 ),pre(Bi )>pre(Ai ) 或 pre(Bi−1)>pre(Ai−1),pre(Bi)≤pre(Ai)\text{pre}(B_{i-1})\gt
\text{pre}(A_{i-1}),\text{pre}(B_i)\le \text{pre}(A_i)pre(Bi−1 )>pre(Ai−1 ),pre(Bi )≤pre(Ai )，则会产生 111 的贡献。把它们分别计作情况 1，情况 2。
情况 1
显然前 i−1i-1i−1 要在 [1,pre(Ai−1)][1,\text{pre}(A_{i-1})][1,pre(Ai−1 )] 之间选，iii 要在 (pre(Ai),n](\text{pre}(A_i),n](pre(Ai ),n] 之间选，剩下的随便选。总情况数为 (pre(Ai−1)i−1)(i−1)!(n−pre(Ai))(n−i)!{\text{pre}(A_{i-1})\choose i-1}(i-1)!(n-\text{pre}(A_i))(n-i)!(i−1pre(Ai−1 ) )(i−1)!(n−pre(Ai ))(n−i)!。
情况 2
前 i−1i-1i−1 都要在 [1,pre(Ai)][1,\text{pre}(A_i)][1,pre(Ai )] 选，但必须至少有一个要大于 pre(Ai−1)\text{pre}(A_{i-1})pre(Ai−1 )。这太难了。
考虑反向统计，总方案数为 (pre(Ai)i−1)(i−1)!{\text{pre}(A_i)\choose i-1}(i-1)!(i−1pre(Ai ) )(i−1)!，不合法的有 (pre(Ai−1)i−1)(i−1)!{\text{pre}(A_{i-1})\choose i-1}(i-1)!(i−1pre(Ai−1 ) )(i−1)!，所以合法的有 [(pre(Ai)i−1)−(pre(Ai−1)i−1)](i−1)!。
再用方案 1 同种方法考虑后面的，总贡献数为 [(pre(Ai)i−1)−(pre(Ai−1)i−1)](i−1)!(pre(Ai)−i+1)(n−i)!(\text{pre}(A_i)-i+1)(n-i)!(pre(Ai )−i+1)(n−i)!。
时间复杂度：O(n)O(n)O(n)。
record
