【题解】AT3954 [AGC023C] Painting Machines

AT3954 [AGC023C] Painting Machines

\(\text{Solution:}\)

首先可以考虑对每个数拆贡献,一个数如果有贡献显然是它自己有贡献或者排在它后面的数有贡献。

这个东西看起来就不好做。所以直接容斥掉,变成求它有多少情况不贡献。

此时当且仅当它后面的数和它自己全部没有贡献。

那么从这一步开始,我们发现,这个数具体是多少已经不重要了,我们现在只需要知道,有多少长度为 \(i\) 的后缀,其全部没有贡献。

现在需要明确一下:先考虑转化为 有多少长度为 \(i\) 的排列可以覆盖全部格子。 接下来我们发现,后面的 \(n-i-1\) 是可以随便排列的,而前面这 \(i\) 个也是可以随便排的,现在就剩下如何确定有多少种方案有 \(i\) 个可以覆盖所有格子。

剩下就是我没有想到的地方了)

考虑设集合为 \(S\) (由于之前把随便排给去掉了,所以此时是没有顺序的,后面要乘一个 \(i!\times (n-i-1)!\) )

那么不妨认定它是有顺序的,它需要满足下列条件:

  • \(1\in S,n-1\in S\)
  • \(\forall i,S_{i+1}-S_i\leq 1\)

第一步是因为 \(1,n\) 只能被这样覆盖,第二步是因为,如果不满足,那么 \(S_i+2\) 就无法覆盖。

考虑怎么求 \(S\) 的个数。我们发现,现在可以从元素位置差的角度来考虑。

首先要发现一个性质:\(\left(\sum S_i-S_{i-1}\right)=n\)

那么考虑这个间隙应当满足什么条件:设 \(|S|=t,\) 则我们需要空出 \(n-t-1\) 个位置,而一共有 \(t\) 个元素,所以一共有 \(t-1\) 个空隙。

那么不妨表示为方程,则有:

\[\sum _{i=1}^{t-1} x_i=n-t-1,x_i\in\{0,1\} \]

考虑生成函数,将每个 \(x\) 写成 GF 形式,所求即为:

\[F=\prod_{i=1}^{t-1} (1+x) \\ Ans=[x^n]F(x) \]

考虑其 \(n\) 次项的系数,容易发现这个是杨辉三角。

那么就有:

\[Ans=\binom{t-1}{n-t-1} \]

于是整理上述过程,设 \(f_i=\binom{t-1}{n-t-1},\)

\[Ans=\sum f_i\times i!\times (n-i-1)! \]

组合意义就是:找到大小为 \(i\) 的合法集合方案数,集合内部随便排,外部随便排。注意其不能交叉,是因为这里强制了 \(S\) 排在前面。

预处理阶乘就可以线性了。

止步在了容斥完的地方……思维跑到分两端组合了,后面一段的阶乘想到了,问题在于没有想到前面一段可以乘阶乘去掉顺序之后有一个差 \(\leq 1\) 的限制,利用限制化为方程解数求解的方法。

上一篇:奇异值分解 上篇


下一篇:素数与筛法