首页 > 其他分享 >CF div3 998(F,G)

CF div3 998(F,G)

时间:2025-01-20 17:55:22浏览次数:1  
标签:sum 交换 CF len 998 数组 ans div3 dp

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}\)。

code

G

思维 + \(dp\)

首先显然可以发现:任意一列的两个数一定是绑定在一起的,比如\((a,b)\)在同一列,则不管怎样操作,\((a,b)\)始终都会在同一列。

那么,最终形成的序列一定满足该性质:对于所有列,按每一列中的最小值升序排序,证明略。

同时,可以发现某一种交换方式,使得任意两列可以交换,并且不改变任何一列内数的上下关系,如下图:

pEkH5m4.png

根据以上两点就可以发现:将原序列按列的最小值升序排序后的合法性,与检查原序列的合法性是等价的。

因为可以交换任意列,所以总是可以将原序列变为按最小值升序排序的序列,而同时所有列按最小值升序排序又是满足合法性的必要条件,因此得证。

那么剩下的问题就转变为了检查上下数交换的合法性。由下图的操作可以发现,也可以同时交换任意两列的上下两个数:

pEkbEjS.png

所以上下数交换的次数一定是偶数。

考虑\(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\)列的所有状态(是否翻转),通过检查是否满足两列有序来决定是否转移。具体转移细节见代码。

code

标签:sum,交换,CF,len,998,数组,ans,div3,dp
From: https://www.cnblogs.com/jjjxs/p/18680734

相关文章

  • CF1253F Cheap Robot
    CheapRobot题目翻译:给一个带$N$个点的带权无向连通图,并给定$k$每经过一个边就要消耗边的边权$w$,而当到达$1\simk$的节点处可以将点充满。求从$a$到$b$所需要的最小点容量$c$。及一次性消耗的电量不能超过$c$。前置知识:$1.$最近公共祖先$LCA$$2.$最小生成树$kruskal$$3.$......
  • 题解:CF580B Kefa and Company
    CF580BKefaandCompany前言。其实本题与这道题极为相似,所以建议降橙。思路因为输入顺序不影响就结果,所以可以先给\(a\)按照工资从小到打排序一下序(这里\(a\)使用MAP)。然后再使用尺取法,只要\(a_{r+1}\)的值减\(a_l\)的值\(\ltk\)就将\(r\)加\(1\)。然后发现每......
  • CF 265B.Roadside Trees (Simplified Edition)(Java实现)
    题目分析    松鼠的起点在第一棵树的0位置,它的行动轨迹为到达顶端,吃坚果,到另一棵树的同位置,到达顶端,吃坚果。思路分析    根据题目分析,我们需要有一个不断更新的起始位置,单次循环内的时间=到达顶端的距离+吃坚果+跳跃=顶端-起始+1+1代码        ......
  • CF 284B.Cows and Poker Game(Java实现)
    题目分析    奶牛也打扑克。一共有三种情况,简称AFI,并且只有自己为AI状态其余全部人为AF状态才可以亮手牌。思路分析    根据题目分析,针对三个不同状态分析情况:当且仅当有一个I时,唯有这个奶牛可以亮牌,如果I的个数大于1,一个也不能亮牌;当没有I时,判断A的个数,有......
  • 「CF 123E」Maze
    传送门题意澄清对于dfs遍历时,在某一个点进入子树的顺序并不是按输入顺序,而是假定随机选择未进入过的子树(这纠结了我好久)。破题思路首先可以明确这题不能推一个\(O(1)\)的式子来计算期望(树的结构是随机的,对于所有点不存在均摊期望的可能),但是对于某一刻子树以根节点......
  • CF516E Drazil and His Happy Friends 做题记录
    CF516EDrazilandHisHappyFriendsDescription有\(n\)个男生\(m\)个女生,编号分别为\(0\simn-1\)和\(0\simm-1\)。有\(B\)个男生和\(G\)个女生是快乐的,其他人是不快乐的。在第\(i\)天,编号为\(i\bmodn\)的男生和编号为\(i\bmodm\)的女生会一起......
  • 1998-2014年中国工业用水数据集
    中国工业用水数据集是根据全国各地单独报告的工厂级水资源信息汇编而成的。这种来自微观水平工厂报告的独特DGP的粒状数据不同于所有其他研究甚至官方统计中基于固定部门特定水密度的宏观水平估计。它包含了1,480,265个工厂每年的观察,提供了前所未有的细节和对水使用模式的洞察......
  • 题解:CF140A New Year Table
    CF140ANewYearTable思路注意到题目中提到了大圆与小圆相切,我们可以计算由两条经过小圆周长与大圆圆心的切线组成的圆心角的度数。但是这个角度其实不好算,所以我们可以求出它一半的正弦值,也就是\(b\div(a-b)\),然后用asin函数求出其度数(以弧度为单位)。最后答案就是判断\(......
  • [CF2048F] Kevin and Math Class 题解
    注意到这里有个区间的\(b_i\)最小。我们考虑每个\(b_i\)作为最小的时候各操作几次。显然每个\(b_i\)的【操作区间】更长是不劣的。于是这些个\(b_i\)是可以打成笛卡尔树,进行DP。想到这一点,DP便是不难的了。定义\(f_{i,j}\)为以\(i\)为根的子树内,最优操作后最大值......
  • AI绘画模型王者归来,majicFlus 模型重磅发布!
    要说SD社区中最受欢迎的大模型,那就必然是麦橘系列了——SD1.5时代的神,majicMIXrealistic麦橘写实模型更是一口气霸占了lib社区最热、最多运行、最多下载三榜第一、最多返图(第二),光lib一个平台就将近1500w的在线运行量,26w的下载量,以往大家说的一脸AI很大程度上......