BZOJ 3811: 玛里苟斯
UOJ Round的一些题

ProjectEuler 559

YYY posted @ 2016年5月13日 12:50 in 算法竞赛 with tags 生成函数 组合数学 容斥原理 多项式求逆 , 1269 阅读
_THIS_IS_START_OF_ARTICLE_
----------------------------------------------------------
原则上是不该在博客里写PE的题解的,而且我这个题的做法也慢的要死(跑了几分钟)
但是搞了好久,感觉不写一下题解不舒服,所以还是来写一下我这个naive的做法
 
另外这道题我是第52个过的,QAQ
 
----------------------------------------------------------
这是一道大题
 
题意:一个矩阵的第$i$列称作是上升的,当且仅当这一列每个元素都小于第$i+1$列同行元素,一个$n$阶方阵是k-合法的,如果这个方阵的第$j$列是上升的,当且仅当$j$不是$k$的约数且$j≠n$(因为最后一列没有下一列,所以最后一列不可能上升),并且这个方阵的每一行都是$1$~$n$的排列,设这样的方阵个数是$f(k)$,对于$n=50000$,求$\Sigma_{k=1}^{n}f(k)$
 
为了方便,除了上升的定义之外,再定义一种列叫任意列,任意一个列都是任意列
首先考虑枚举$k$,然后考虑容斥(为了方便,一列的编号如果是$k$的倍数,就说他是kk列)
记$r[i]$=除了有$i$个kk列是上升列外,所有kk列都是任意列,非kk列都是上升列的$n$阶方阵数
不难发现答案就是$p[k]=r[0]-r[1]+r[2]-...=\Sigma_{i=0}^{\lfloor n/k \rfloor}(-1)^{i}r[i]$
 
现在来考虑$r[i]$怎么求
显然他的每一行都满足$r[i]$的定义(只是把方阵换成向量)
现在考虑编号为$k$的倍数的位置,显然要选$i$个编号是$k$的倍数的位置,在他们后面填上<号,然后剩下的$\lfloor n/k \rfloor - i$个$k$的倍数的位置,他们后面填上?号(表示>或者<都可以),其余元素后面都填上<号
显然整个序列就被?号分成了$\lceil n/k \rceil - i$块,每一块以内只要有哪些元素确定了,这一块就确定了(因为块内是排好序的)
设$b$是块数也就是$b=\lceil n/k \rceil - i$,设每块大小分别为$a1,a2,..ab$,那么最后答案就是$n$个元素中选$a1$个涂上颜色$1$,选$a2$个涂上颜色$2$..的方案数,
也就是$(x_{1}+x_{2}+...+x_{b})^{n}$的$(a1,a2..ab)$次项系数,根据多项式定理,它就是$n!/(a1!*a2!*...*ab!)$
那只需要求出这样的排列数再$n$次方一下,然后对所有可行的$b$维向量$(a1,a2..ab)$求和就行了
(注意这里除了$ab$之外,所有的$ai$只能取$k$的倍数,而$ab$必须取$k$的倍数$-(n$ $mod$ $k)$)
设$n$ $mod$ $k$ $= d$
因此$ai(i<=b-1)$能取的集合是$S=${$k,2*k,..,+∞*k$},而$ab$能取的集合是$S'=${$k-d,2*k-d,..,+∞*k-d$}
再观察一下计算答案的表达式,因为最后要$n$次方,因此答案实际上是:
$(n!)^{n} / (\Sigma_{a1+a2+..+ab=n}\Pi_{i=1}^{b}(ai!)^{n})$
只需要求$s_{b}=(\Sigma_{a1+a2+..+ab=n}\Pi_{i=1}^{b}(ai!)^{n})$
发现可以用生成函数搞
设$A=\Sigma_{ai \in S}x^{ai}/((ai!)^{n})$
$A'=\Sigma_{ai \in S‘}x^{ai}/((ai!)^{n})$
设$P[k]$表示多项式$P$的$k$次项系数
显然$s_{b}$就是$n!*((A^{b-1}*A')[n])$
为了方便设$w=b-1$好了
而$A'$可以放到最后再乘,$n!$也可以放到最后再乘
因此现在就是要求$O_{k}=\Sigma_{i=0}^{n}(-1)^{i}*A^{w}$来求出$k$的答案
设$h=\lceil n/k \rceil$
然后YY一下发现$O_{k}=A^{h}-A^{h-1}+A^{h-2}-..+(-1)^{h}A^0$
然后发现有加有减的十分蛋疼,因此可以把$O_{k}$中的奇偶项分别考虑一下
为了方便,不妨先假设$0$次项系数是$-1$(也就是奇数项减偶数项),最后再判一下$b$的奇偶,不对再乘一个$-1$就行了
然后因为$A$的$0$次项为$0$,因此多乘一些也没有关系
因此奇数项是偶数项乘以$A$,而偶数项是$\Sigma_{i=0}^{+∞}(A^2)^i=1/(1-A^{2})$
因此奇数项减偶数项就是$(A-1)/(1-A^{2})=-1/(1+A)$
因此只需要求$4-(1+A)$的倒数就行了,然后再看一下要不要乘以$-1$,最后再乘以$A'$(注意,这里乘的时候,因此只关心$n$次项系数,因此可以是$O(n)$的),再把$n$次项系数拿出来乘以$(n!)^{n}$作为$k$的答案就行了,把$k$的答案累加就是最后的答案了
时间复杂度$O(n^{2}*log)$,其中$log$来源于多项式求逆
 
实际上我实现的时候,多项式求逆里面的卷积是暴力跑的(因为普通的FFT要爆精度,Picks那个我又觉得太麻烦了,于是就先跑了一下暴力,结果跑得意外的快),但是不知道为什么跑得快得飞起,$k$比较大的时候求逆几乎是$O(n)$的,我猜是因为$k$大的时候$A$中的非零项太少(而我求卷积的时候如果某一项为$0$就跳过这一项来加速)
 
答案?嘿嘿嘿不给
----------------------------------------------------------
 

 

_THIS_IS_END_OF_ARTICLE_

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter