首页 > 其他分享 >2023.12 做题纪要 #2

2023.12 做题纪要 #2

时间:2023-12-19 20:56:10浏览次数:39  
标签:系数 frac 2023.12 sum 容斥 GF binom 纪要

感动,居然 12 月还有第二个做题纪要!

目录

2023.12.19

有点太安静了,于是拿耳机听歌写题了(

好像还不错,梦幻联动而且确实挺好听

P7325 [WC2021] 斐波那契

一开始没看数据范围,以为 \(m\) 很大,想半天然后突然意识到数据范围,呃呃。写了个试试,啥,咋就直接过了。

首先有皮那啥周期,所以循环节是 \(O(m)\) 的,我们只需要考虑这 \(O(m)\) 项里面有没有 \(0\)。

但是状态太多了,你不能 \(O(m^2)\) 枚举所有点对吧。考虑减少点有用数对。

注意到问什么时候有 \(0\),那么我们给整个序列乘一个数这个答案是不变的。那么我们可以考虑乘个逆元把 \(a\) 或者 \(b\) 变成 \(1\)。

但是问题是万一逆元都不存在呢?这时候 \(\gcd(a, b, m) = w > 1\),我们可以把三个值全除以 \(w\) 就行了。容易发现这个操作只需要最开始来一次就够了。

那么每次将 \(a/b\) 变成 \(1\),这样就只剩下 \(O(m)\) 对值了,而不同的模数只有 \(d(m)\) 种,每种模数的状态和就是因数和,于是总复杂度就是 \(O(\sigma(m) \log m)\),\(\log\) 是求逆元的复杂度。

题解做法咋都这么麻烦??

P8354 [SDOI/SXOI2022] 多边形

怎么题单里有个 GF 题。

考虑这个题实际上是加了一些限制的三角剖分,没有限制的三角剖分是卡特兰数 \(C_{n-2}\),而这里的具体限制是:可以将同一边中的多个边合并起来,然后要求同一边之间不能有连边。

合并过程直接枚举合并成几段,然后组合数算一下,那么考虑同一边不能有连边咋整。

考虑容斥,我们以同一边连边的数量容斥,仔细推一下发现我们只用统计只跨过两条边的不合法集合,因为如果有跨过更多边的不合法边,那么这条不合法边里面连的边都是不合法的,而把这个集合内的容斥系数加和等于 \(0\)。

那么问题就是,可以在同一边选若干跨过两条边的不合法边,然后再乘上里面三角剖分的方案数。我们只需要考虑求出每种内部多边形边数的容斥系数之和即可计算答案,而显然每一边的容斥系数是独立的,我们可以先求出每一边然后再分治乘法乘起来。

现在只考虑一边,我们的问题是:现在有 \(n\) 条边,将若干条边缩起来,然后将剩下的边划分成长度为 \(1\) 或 \(2\) 的段,每个 \(2\) 的容斥系数是 \(-1\),对每种段数求所有容斥系数之和。

接下来是互动博客,请选择你的路线:

我们可以把两步操作合起来去做,因为实际上我们可以看做先划分 \(1\) 或 \(2\) 段,然后在中间接着划分缩起来的边,那么设 \(f_{i, 0/1/2}\) 表示第 \(i\) 条边在 \(1\) 段,还是在 \(2\) 段的前一部分或后一部分,可以无脑矩阵快速幂,这里比较有趣的是矩阵快速幂的复杂度是 \(O(n \log n)\) 的而不是两个 \(\log\),因为矩阵没有被取模,这个过程相当于倍增。或者你把 DP 写成更好倍增的形式,都行吧。

哦 dottle 说 9 倍就会 TLE,没事了,其实存在 8 倍的 DP,摆了。

考虑推下式子:先枚举划分成多少段,然后枚举选几段 \(2\),设这边一共有 \(n\) 条边,那么容易发现我们就是要求:

\[\begin{aligned} F_n(x) &= \sum_{i=0}^{n} \binom{n - 1}{i - 1} \sum_{j=0}^i \binom{i - 2j + j}{j} (-1)^j x^{i - 2j + j}\\ &=\sum_{i=0}^{n} \binom{n - 1}{i - 1} \sum_{j=0}^i \binom{i - j}{j} (-1)^j x^{i - j}\\ &=\sum_{k=0}^n x^k \sum_{i=0}^{n} \binom{n - 1}{n - i} \binom{k}{i - k} (-1)^{i - k}\\ \end{aligned} \]

也就是说,我们要求出一个数组 \(f_k = \sum_{i=0}^{n} \binom{n - 1}{n - i} \binom{k}{i - k} (-1)^{i - k}\)。但是我们迎来了 \(i, k - i, i + k\) 三个下标,没法直接卷积了,哈哈!

组合意义的尽头是代数推导。

考虑拿 GF 刻画一下,引入个元 \(x\),将上式写成 \(n-i\) 与 \(i-k\) 的卷积形式,即:

\[f_k = [x^{n - k}] (1+x)^{n-1} (1-x)^k \]

这下长得足够抽象了,请选择你的路线:

大力莽一下,记 \(G_k(x) = (1+x)^{n-1} (1-x)^k\),求个导得:

\[\begin{aligned} G'_k(x) &= G_k(x) \left(\frac{n-1}{1+x} - \frac{k}{1-x}\right)\\ (1-x^2) G_k'(x) &= (n-1-k) G_k(x) - (n-1+k) x G_k(x)\\ (i+1) g_{k,i+1} &= (n - 1 - k) g_{k,i} - (k + n - i) g_{k,i-1}\\ \end{aligned} \]

然后还有 \(G_{k+1}(x) = G_k(x) (1-x)\),所以有 \(g_{k+1,i} = g_{k, i} - g_{k,i-1}\)。

那你要求的是 \(g_{k,n-k}\),你就可以 \(O(n)\) 递推了。

有 \(f_k = [x^n] (1+x)^{n-1} (x-x^2)^k\),拆一下有 \(f_k = \sum_{i=0}^n [x^{n-i}] (1+x)^{n-1} [x^i] (x-x^2)^k\),记 \(g_i = [x^{n-i}] (1+x)^{n-1}\),那么就是 \(f_k = \sum_{i=0}^n g_i [x^i] (x-x^2)^k\)。

转置一下,考虑求 \(g_i = \sum_{k=0}^n f_k [x^i] (x-x^2)^k\) 的算法,发现这就是在求多项式 \(F(x-x^2)\),那么就拆一下,有 \(F(x-x^2) = F(-(x-\frac 12)^2 + \frac 14)\),那么有流程:

  • \(F(x) \gets F(x + \frac 14)\);
  • \(F(x) \gets F(-x)\);
  • \(F(x) \gets F(x^2)\);
  • \(F(x) \gets F(x - \frac 12)\)。

于是转置过来做就可以了,复杂度 \(O(n \log n)\)。

因为我第一次学转置原理,所以需要写一下多项式平移咋转置(

首先多项式平移实际上是:

\[F(x+b) = \sum_{i=0}^n \frac{x^i}{i!} \sum_{j=0}^n j! f_j \frac{b^{j-i}}{(j-i)!} \]

令 \(G(x) = \sum \frac{b^i}{i!} x^i\),那么上述过程可以看做是:

  • 将 \(F(x)\) 的各项系数乘 \(i!\);
  • \(F(x) \gets F(x) \times^T G(x)\);
  • 将 \(F(x)\) 的各项系数除以 \(i!\)。

那么转置就是先除以 \(i!\),然后正常乘一个 \(G(x)\),然后再将系数乘 \(i!\)。

考虑直接大力 GF 表示答案,考虑每一段要不然是一段,要不然是两段拼起来的,一端的系数 GF 就是 \(\frac{w}{1-w} - (\frac{w}{1-w})^2 = \frac{w(1-2w)}{(1-w)^2}\),那么答案 GF 就是 \(\sum_{k\ge 0} x^k [w^n] \left(\frac{w(1-2w)}{(1-w)^2}\right)^k\)。

请选择你的路线:

无所谓,我是无脑选手。把上面的式子直接写成二元 GF 的形式,要求的就是 \([w^n] \frac{1-2x+x^2}{1-(x+2)w+(1+2x)w^2}\),可以无脑 Bostan-Mori 求,每次需要 8 次多项式乘法。

dottle:实测 9 次会 T,8 次可以。

直接拉反,令 \(u\) 为 \(\frac{w(1-2w)}{(1-w)^2}\) 的复合逆,那么有:

\[[w^n] \left(\frac{w(1-2w)}{(1-w)^2}\right)^k = \frac{k}{n} [x^{n-k}] \left(\frac{x}{u}\right)^n \]

可以直接暴力全家桶求出来,或者 ODE 线性求出来。

标签:系数,frac,2023.12,sum,容斥,GF,binom,纪要
From: https://www.cnblogs.com/apjifengc/p/17912879.html

相关文章

  • 【笔记】2023.12.19:题目选讲
    笔记2023.12.19:题目选讲不会的题目没在这里展现。一共14道题。gym103371IOrganizingColoredSheets猜结论:两个同一行的sharp的间隙的\(\min\)是\(W\)上界,同一列的sharp的间隙的\(\min\)是\(H\)上界,然后相乘。这是假的,是答案上界,过不去样例二。每个\(H\)对......
  • 2023.12.18
    点击查看代码#include<bits/stdc++.h>#definefifirst#definesesecondusingstd::cin;usingstd::min;usingstd::max;usingstd::cout;usingstd::vector;constexprintM=2e6+5;constexprintINF=0x3f3f3f3f,mod=998244353;......
  • [2023.12.14] 大学 & XCPC小记
    说起来OI退役多年,已经很久没有维护过这个博客。上一周打完ICPC杭州站,也是大三赛季的最后一站,总觉得应该记一些什么……不止是记录我的XCPC生涯,也是给大学的前面快要5个学期做一个大体上的总结吧~ 一切都还要从高考结束开始说起。2021.6  高考&暑假篇高考结束,......
  • 2023.12.18——每日总结
    学习所花时间(包括上课):9h代码量(行):0行博客量(篇):1篇今天,上午学习,下午学习;我了解到的知识点:1.JFinal明日计划:学习......
  • 闲话 2023.12.18
    前天晚上打了CodeforcesRound915(Div.2),打的最好的一次,成功实现上大分......
  • 云原生周刊:Kubernetes v1.29 正式发布 | 2023.12.18
    开源项目推荐RobustaKRRRobustaKRR(KubernetesResourceRecommender)是一个用于优化Kubernetes集群中资源分配的CLI工具。它从Prometheus收集Pod使用数据,并建议CPU和内存的请求和限制。这降低了成本并提高了性能。LiqoLiqo是一个开源项目,可实现动态、无缝的Kuber......
  • (2023.12.18)wifi的频宽配置
    //网关设备上的WiFi问题单ht_capab:频宽可调HighThroughput高吞吐量能力参数VHT:VeryHighThroughput现在也叫WiFi5GuardInterval:保护间隔(无线提速参数)AX2和AX5:指的是2.4G频段和5G频段HT40+:次通道高于主通道HT40-:次通道低于主通道SHORT-GI-20:disabledifnotsetWPA2:体......
  • 2023.12 English四级 作文
    《2023年12月英语四级作文真题及范文(三套全)》最深刻的一次校园活动作文1Supposeyouruniversitynewspaperisinvitingsubmissionsfromstudentsforitscomingeditiononacampuseventthathasimpressedthemmost.LastSaturday,ourStudentU......
  • 2023.12 六级 English 作文
    《2023年12月英语六级作文真题及范文网络版(三套全)》作文1:TheimportanceofacquiringthebasicknowledgeAsweallknow,masteringgoodbasicknowledgeisanimportantstepthateverystudentmustgothroughinthelearningprocess,anditiscrucial......
  • 2023.12.16——每日总结
    学习所花时间(包括上课):9h代码量(行):0行博客量(篇):1篇今天,上午学习,下午学习;我了解到的知识点:1.c#明日计划:学习......