A
枚举其中一个,然后发现剩下两个的限制非常强,用一个桶统计同余类大小即可。
B
谔谔构造。
考虑 \(n=\log 10^6\),大概可以猜一下这个题是想让我们搞一个二进制构造。
先造一条 \(0\sim 2^{\log L}-1\) 的链,然后再往 \(N\) 连即可。
C
基础组合题。不是很懂为啥题解里都是容斥原理,范德蒙德卷积的形式感觉还是挺显然的。
考虑有 \(s\) 个互斥对时如何计算答案。
\[\begin{aligned} f(s) & =\sum\limits_{i=1}^{k-s}\sum_{j=1}^s \binom{n-1}{i-1}\binom{s}{j}\binom{k-2s}{i-j}2^j\\ & = \sum_{j=1}^s \binom{s}{j}2^j\sum_{i=1}^{k-s}\binom{n-1}{n-i}\binom{k-2s}{i-j}\\ & = \sum_{j=1}^s \binom{s}{j}2^j \binom{n-1+k-2s}{n-j} \end{aligned} \]直接计算即可。
D
思维 & 结论题。
考虑 \(p_i\) 操作以后肯定就没法动了,所以必然有 \(p_i=i\)。这一步感觉很精妙,可能需要多手玩一些样例。
然后考虑判定。定义 \(a_i=[p_i=i]\),如果 \(a\) 中连着 3 个 0 显然就废了。否则可以拆出来若干 \(010101\dots\) 这样的段。考虑每一段内,\(p\) 值都必须在下表范围内,并且 \(a\) 为 0 的位置不能产生 \(>2\) 的下降子序列。画一画大概就清楚了/yun。
不是很懂 tzc_wk 的逆序对做法怎么证明正确性。maybe prove by AC。
标签:log,2s,sum,ARC102,binom,考虑 From: https://www.cnblogs.com/Royaka/p/17785552.html