数数的群星闪耀时

标签：数数 code 2p sum 群星 binom prod 闪耀 复杂度

科技博客里都有，这里主要是个杂题乱做。

常用简单技巧：

• 多条件至少满足一个直接容斥。
• 至少和恰好直接二项式反演。
• 组合意义，组合意义。
• 生成函数直接上。
• 别组合魔怔了，可以 dp。

ABC285Ex *3192 \(\color{blue}\bigstar\)

显然每个 \(p_i\)，相当于把 \(E_i\) 拆成若干个奇数和偶数放到 \(n\) 个数上，要求每个数至少分到一个奇数。

简单 dp 是直接设 \(f_{i,j}\) 表示前 \(i\) 个 \(E_i\)，已经有 \(j\) 个数分配到了奇数的方案数，然后直接暴力枚举选多少个奇数以及怎么放，复杂度 \(O(n^4)\)，code。放的方法就是先放一堆 \(1\)，然后剩下有一堆 \(2\) 插板法乱放。

容斥一下，枚举一下有多少个数是完全平方数，得到：

\[\sum_{i=0}^n (-1)^i \binom{n}{i}\prod_{j=1}^K \sum_{p=0}^{a_j/2}\binom{n-i}{a_j-2p}\binom{n-1+p}{n-1} \]

复杂度 \(O(n^3)\)，code

后面那两个东西中含有一个 \(2p\)，比较难搞，上生成函数。

\[\sum \binom{n-1+p}{n-1}x^{2p}=\frac{1}{(1+x^2)^n}\\ \sum \binom{n-i}{a_j-2p}x^{a_j-2p}=(1+x)^{n-i}\\ \sum_{i=0}^n (-1)^i \binom{n}{i}\prod_{j=1}^K \sum_{p=0}^{a_j/2}\binom{n-i}{a_j-2p}\binom{n-1+p}{n-1}\\ = \sum_{i=0}^n (-1)^i \binom{n}{i}\prod_{j=1}^K [x^{a_j}]\frac{(1+x)^{n-i}}{(1+x^2)^n} \]

可以发现后面那个东西已经和 \(j\) 无关了，因此可以暴力求出 \(\dfrac{(1+x)^{n-i}}{(1+x^2)^n}\) 然后算 \(K\) 个点值即可。

这个东西相当于每次乘一个 \((1+x)\)，单次乘复杂度 \(O(n)\)，因此直接暴力做即可，复杂度 \(O(n^2)\)。

code

ABC284G *2218 \(\color{green}\bigstar\)

显然答案算的是连成一个基环树之后每个点走到一个环的步数。

直接拆贡献，考虑枚举链的长度以及环的大小。

\[\sum_{i=1}^n \sum_{i+j\le n} \binom{n}{i}i!\binom{n-i}{j}j!(i-1)n^{n-i-j} \]

由于读入模数，所以组合数显然要扔掉。

化简一下，变成

\[\sum_{i=1}^n \sum_{i+j\le n} \frac{n!}{(n-i-j)!}(i-1)n^{n-i-j} \]

变成了一个只和 \(i+j\) 有关的式子，\(\dfrac{n!}{(n-i-j)!}\) 相当于是一个后缀积，因此直接考虑每个 \(i+j\) 的贡献就可以做到 \(O(n)\)。

code

LNR#2D1T3 \(\color{Gold}\bigstar\)

只会 \(O(n^2)\) dp，这个 dp 还是比较套路，设 \(f_{i,j}\) 表示前 \(i\) 个数已经填了 \(1\) 到 \(i\) 的排列，第 \(i\) 个数填了 \(j\) 的方案数，加一个就相当于是插入一个位置即可。

转移就是 < 就后缀和，> 就前缀和。

这个东西不太能优化，寄。

想想能不能容斥，如果直接令一些位置不合法，不太可做。

一个很妙的是，如果把 > 这些位置改成没有限制，那么相当于是一堆递增的序列，假设这些序列长度分别为 \(a_i\)，那么总方案数就是

\[\frac{n!}{\prod (a_i)!} \]

那么，我们直接对于所有 > 进行容斥，钦定一些位置强制改成 <，剩下位置随意，这样方案数好算。

直接 dp，设 \(f_i\) 表示第 \(i\) 个位置是 > ，前 \(i\) 个的方案数，为了方便，我们只算 \(\frac{1}{\prod (a_i)!}\) 部分，上面的最后乘上。

枚举上一个 > 的位置，可以得到

\[f_i=\sum_{j=0}^{i-1} f_j\times (-1)^{s_i-s_j-1} \times \frac{1}{(i-j)!} \]

\(s_i\) 是 > 的前缀和。

转移需要满足 \(i,j\) 都是 >。暴力做 \(O(n^2)\)。

发现后面是一个卷积形式，直接分治 FFT 即可，复杂度 \(O(n\log^2 n)\)。

code

LNR#2D2T2 \(\color{blue}\bigstar\)

可以发现 \(p\) 很小，就可以用 Lucas 定理，已知生成函数，要找到他的组合表达式。

\[Ans=[x^k](\sum_{i=0}^n a_ix^i)^m\\ = \sum_{\sum b_i=m}\binom{m}{b_1,b_2,...,b_n} \prod(a_ix^i)^{b_i}\\ = \sum_{\sum b_i=m,\sum ib_i=k} \binom{m}{b_1}\binom{m-b_1}{b_2}... \prod a_i^{b_i} \]

可以发现中间一坨组合数，去模 \(p\) 要不等于 \(0\)，容易想到对 \(m\) 转成 \(p\) 进制，那么每一位上都必须满足 \(b_i\) 之和等于 \(m\)，因此可以每一位单独考虑。

因此我们可以先预处理一下 \(<p\) 的幂次，这个部分是 \(O(n^2p^2)\)，然后进行数位 dp，从高到低一次使得 \(\sum b_i=m,\sum ib_i=k\) 成立，又因为 \(a^p\bmod p=a\)，所以后面的贡献与数位无关，直接做即可。

总复杂度 \(O(n^2p^2+Tn^2\log_p m)\)。

code

标签：数数,code,2p,sum,群星,binom,prod,闪耀,复杂度
From： https://www.cnblogs.com/houzhiyuan/p/17077390.html