ProjectEuler 559
_THIS_IS_START_OF_ARTICLE_
_THIS_IS_END_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$就跳过这一项来加速）
答案？嘿嘿嘿不给
----------------------------------------------------------
评论 (0)
