F
\(dp\) + 组合数学
需要注意,数组中\(>1\)的数字个数不会超过\(log_{2}k\)个。
先暂时不考虑\(1\)的摆放,只考虑所有\(>1\)的数:
设\(f_{l,i}:\)长度为\(l\),乘积为\(i\),且所有元素均\(>1\)的数组个数
考虑数组的最后一个元素\(d\),必有\(d|i\)成立,因为每个元素一定是\(i\)的因子。
则\(f_{l,i}\)可以由\(f_{l-1,i/d}\)递推而来:
\[f_{l,i} = \sum_{d|i} f_{l-1,i/d} \]设\(ans_i\)表示乘积为\(i\),长度取值范围\([1,T]\)的数组个数,则:
\[ans_i = \sum_{l=1}^{T}f_{l,i} \]其中\(T<=log_{2}k\),可以直接暴力计算得到。
现在需要考虑将数字\(1\)加入到数组中。设加入了\(j\)个\(1\),则新数组的长度为\(l+j\),\(j\)可能取值范围是\([0,n-l]\)。加入\(j\)个\(1\)后的方案数还需要考虑\(>1\)的\(l\)个数在\(l+j\)个位置中的哪些位置。
则\(ans_i\)表达式变为:
\[ans_i = \sum_{l=1}^{T}(f_{l,i} * \sum_{j=0}^{n-l}C_{l+j}^l) \]其中\(\sum_{j=0}^{n-l}C_{l+j}^l\)这部分枚举计算的复杂度为\(O(n)\),不可接受。故考虑优化:
由公式:
\[\sum_{len=l}^{n}C_{len}^{l} = C_{n+1}^{l+1} \]故上式改写为:
\[ans_i = \sum_{l=1}^{T}(f_{l,i} * C_{n+1}^{l+1}) \]其中\(T\)不会超过\(log_{2}k\),故复杂度不会与\(n\)有关,只与\(k\)有关。
计算\(C_{n+1}^{l+1}\):不能直接用逆元法来求,因为\(n\)很大,不能预处理。考虑到\(l<=logk\),故可以直接根据组合数的定义式,暴力枚举\(l\)来求所有的 \(C_{n+1}^{l+1}\)。(详细见代码)
复杂度分析:主要在于递推\(f\)数组的过程。枚举数组的乘积是谁\(O(k)\),计算因子数量\(O(\sqrt{k})\),枚举数组长度\(O(logk)\),故总复杂度为\(O(k\sqrt{k}logk)\)。
关于公式\(\sum_{len=l}^{n}C_{len}^{l} = C_{n+1}^{l+1}\)的证明:
\[ \sum_{len=l}^{n}C_{len}^{l} = C_{l}^{l} + C_{l+1}^{l} + ... + C_{n}^{l} \]将 \(C_{l}^{l}\) 改为 \(C_{l+1}^{l+1}\),由公式 $C_{n}^{m} = C_{n-1}^{m} + C_{n-1}^{m-1} $ 每次计算前两项,最终就只剩一项,即 \(C_{n+1}^{l+1}\)。
G
思维 + \(dp\)
首先显然可以发现:任意一列的两个数一定是绑定在一起的,比如\((a,b)\)在同一列,则不管怎样操作,\((a,b)\)始终都会在同一列。
那么,最终形成的序列一定满足该性质:对于所有列,按每一列中的最小值升序排序,证明略。
同时,可以发现某一种交换方式,使得任意两列可以交换,并且不改变任何一列内数的上下关系,如下图:
根据以上两点就可以发现:将原序列按列的最小值升序排序后的合法性,与检查原序列的合法性是等价的。
因为可以交换任意列,所以总是可以将原序列变为按最小值升序排序的序列,而同时所有列按最小值升序排序又是满足合法性的必要条件,因此得证。
那么剩下的问题就转变为了检查上下数交换的合法性。由下图的操作可以发现,也可以同时交换任意两列的上下两个数:
所以上下数交换的次数一定是偶数。
考虑\(dp\):
\(dp[i][0/1][0/1]\):考虑前\(i\)列,总交换次数为\(j\)(只需要考虑奇偶性,\(0\)为偶数次,\(1\)为奇数次),且第\(i\)列交换了\(k\)次(同\(j\),即相当于第\(i\)列是否翻转)来使得前\(i\)列有序,是否可行。
\(init:dp[0][0][0] = 1\)
$ans = dp[n][0][0] || dp[n][0][1] $(总交换次数只要是偶数次就合法)
转移:由于已经保证了前\(i-1\)列有序,故要保证前\(i\)列有序,只需要保证第\(i-1\)列与第\(i\)列之间有序即可。枚举第\(i-1\)列和第\(i\)列的所有状态(是否翻转),通过检查是否满足两列有序来决定是否转移。具体转移细节见代码。
标签:sum,交换,CF,len,998,数组,ans,div3,dp From: https://www.cnblogs.com/jjjxs/p/18680734