首页 > 其他分享 >ARC102

ARC102

时间:2023-10-24 19:12:59浏览次数:37  
标签:log 2s sum ARC102 binom 考虑

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

相关文章

  • AT4363 [ARC102D] Revenge of BBuBBBlesort!
    题面传送门奇妙的题目。首先有一个看上去很对的做法:我们从\(a_i=i\)向当前序列移动,每次满足当前位置上不满足的第一个,如果换不过去那么就是NO,否则YES。但是很遗憾这个东......