主题

主题

 
   

分治发发糖

  • 扯淡

其实具体一点来说,应该是CDQ(分治)+FFT/NTT。

一般是处理多次卷积的求值。

其实有一些其他的替代方法。不过这也是一个比较经典的方法。

做了一堆题,拿了一道好分析一点的。虽然可能还没有AC……


  • Permutation Graph

原题:ZOJ 3874(已下线)

给出一个1-n的排列,对于任意一个逆序对,在这两个位置连一条无向边。

给出最终每个连通块的元素,求有多少种排列方案。

答案对786433(一个费马素数,原根为10)取模。


个人解法:

这是一道浙江省赛题。由于题目已经不在了,只好找到网上博客,少许两篇,拿到了标程对拍。

首先发现每一个联通块是连续的元素。假设存在两端不连续的部分[l,x)与(y,r]在同一个联通块里面,那我们考虑中间这个断层[x,y],所有比其小的数字都应该在前面,所有比其大的数字都应该在后面。那[l,x)与(y,r]就不会联通。得证。

接下来是DP:

一者,我们发现答案与联通块的组成数字是无关的,只与长度有关。

二者,我们发现这个联通块的方案数之间是相互不影响的。那么我们可以全部变为第一个联通块长度是i的方案数,以方便考虑。

设F[i]表示长度为i的摆放的方案数。考虑补集法:

  1. 总共的放置方法是k!的。

  2. 不合法的方案就是存在了一个前缀,可以构成一个联通块。

也就是说:F[k]=k!-sigma(F[k-i]*i!) i∈[1,k-1]

这就是一个卷积,左边系数是F[k-i]右边系数是func[i]=i!。然后由于模数是费马素数,我们就用NTT好一些。

先预处理出阶乘。然后CDQ分治。

在一个递归子结构,拿F[l,mid]卷积A[1,r-l+1]即可。

如图所示:


计算红色部分的时候,会在计算贡献的只有绿色与红色部分。递归结构里面可以全部计算到。细细思考一下即可。

代码如下:

https://code.csdn.net/snippets/2258177

 
 
评论
 
 
热度(1)