ABC284F.ABCBAC
直接枚举 \(i\) 然后 \(hash\) 处理即可,记得不要使用自然溢出。
ABC284G.Only One
这题有一个非常关键的性质:每一个点的贡献都是等价的。因此我们只要算出 \(1\) 号节点的贡献,再乘上 \(n\) 即可。
我们考虑贡献怎么算,对于序列 \({1,a_1,a_{a_1}}......\) 我们记 \(l\) 为最靠后的位置,满足前 \(l\) 个数互不相同,第 \(i+1\) 个数就和之前的重复了,构成一个环,记第 \(i+1\) 个数为第 \(p\) 个数,那么 \(1\) 结点的贡献是 \(p-1\) 。因此式子为:
\[\sum_{l=1}^n {n-1 \choose l-1}(l-1)!n^{n-l}\sum_{p=1}^l(p-1) \]由于模数不是质数,所以要把组合数转成下降幂的形式求解。
ABC266G.Yet Another RGB Sequence
关于这一题记录两种做法
直接组合数求解
我们考虑先将 \(k\) 个 \(\text{RG}\) 和 \(b\) 个 \(\text{B}\) 放入序列中,方案数为 \(k+b \choose b\),然后我们考虑将剩余的 \(\text{RG}\) 插入序列之中,我们将序列拼成这个样子:\(\text{...GGGRRR...}\) ,\(\text{...}\) 部分为 \(\text{B}\) 或者 \(\text{RG}\) ,这样构造不会出现新的 \(\text{RG}\) 。计算式为:
\[ans={b+k \choose b}{b+r \choose r-k}{b+g \choose g-k} \]二项式反演
先搬式子
\[f(n)=\sum_{i=n}^m{i \choose n}g(i) \iff g(n)=\sum_{i=n}^m (-1)^{i-n}{i \choose m}f(i) \] 标签:10,...,text,sum,个数,RG,choose,2022.1 From: https://www.cnblogs.com/oscaryangzj/p/17041439.html