Codeforces 1278 F Cards 增强版 题解 (斯特林数,推式子)

原题链接

增强版链接

增强版中k=1e7

为啥网上题解的式子都那么长啊.jpg

首先令\(p=\frac 1m\)。求某个数的次幂的题通常都是无脑转下降幂:\(x^k=\sum_{i=0}^k S_2(k,i)x^{\underline i}\),其中\(S_2\)表示第二类斯特林数,\(x^{\underline i}\)表示下降幂,也就是\(\binom xi i!\)(i>x时值为0)。对于一种实际赢了\(x\)场的情况,\(S_2(k,j)\)对它的答案贡献应为\(\binom xjj!\)。因此我们可以把这个组合数中的每一种选取情况拿出来分别计算贡献,所以最终答案\(=\sum_{j=0}^k S_2(k,j)\binom njj!p^j\),这一步转化也可以列式子推,但是能用组合意义还是用吧。第二类斯特林数是可以\(O(klogk)\)求出一行的,如果NTT板子牛逼的话是可以过这题的,但有\(O(k)\)的做法。

有一个关于第二类斯特林数的公式:\(S_2(k,j)=\frac 1{j!}\sum_{i=0}^j (-1)^{j-i}\binom ji i^k\)。直接带入上面的式子得到:\(ans=\sum_{j=0}^k\sum_{i=0}^j (-1)^{j-i} \frac{n!}{i!(j-i)!(n-j)!}p^ji^k\)。这相当于是我们要把n个元素组成的集合分割成3份,大小分别为\(i,j-i,n-j\)(都可以为0,且前两部分大小之和\(\le k\)),其中第一部分的"权值"为\(i^kp^i\),第二部分的权值为\((-p)^{j-i}\),第三部分的权值为1,求所有分割方式的权值之积的和。我们枚举i,尝试把剩下的权值\(O(1)\)求出。改写一下答案:\(ans=\sum_{i=0}^k i^kp^i f(i)\),其中\(f(i)=\sum_{j=0}^{k-i}\binom{n-i}j(-p)^j\ \ (注意这里的j不是上面的j了)\),我们想要\(O(k)\)求出\(f_0\cdots f_k\)

其实f是可以差分之后递推求的。注意到\(f_k=1\),所以我们反向差分:

\[\begin{align} f_i-f_{i+1}&=(\sum_{j=0}^{k-i}\binom{n-i}j(-p)^j)-(\sum_{j=0}^{k-i-1}\binom{n-i-1}j(-p)^j)\\ &=\binom{n-i}{k-i}(-p)^{k-i}+\sum_{j=0}^{k-i-1}[\binom{n-i}j-\binom{n-i-1}j](-p)^j\\ &=\binom{n-i}{k-i}(-p)^{k-i}+\sum_{j=1}^{k-i-1}\binom{n-i-1}{j-1}(-p)^j\ \ 考虑组合数的递推公式\\ \end{align} \]

再看看这个式子的后半部分等于什么:

\[\begin{align} &\sum_{j=1}^{k-i-1}\binom{n-i-1}{j-1}(-p)^j\\ =&(-p)\sum_{j=1}^{k-i-1}\binom{n-i-1}{j-1}(-p)^{j-1}\\ =&(-p)\sum_{j=0}^{k-i-2}\binom{n-i-1}j(-p)^j\\ =&(-p)(f_{i+1}-\binom{n-i-1}{k-i-1}(-p)^{k-i-1}) \end{align} \]

因此只要预处理一下组合数就能\(O(k)\)求f了,也就是预处理\(g_i=\binom{n-i}{k-i}\),这个很容易\(O(k)\)求。

\(ans=\sum_{i=0}^k i^kp^i f(i)\)中,求出了f还需要\(O(k)\)对所有i求\(i^kp^i\),这个东西是积性的,所以可以线性筛。但是快速幂常数不大所以应该也是可以过的。

时间复杂度\(O(k)\)。下面代码里用了快速幂,是\(O(klogk)\),没有特意去卡洛谷上的时间和空间。

点击查看代码
#include <bits/stdc++.h>

#define rep(i,n) for(int i=0;i<n;++i)
#define repn(i,n) for(int i=1;i<=n;++i)
#define LL long long
#define pii pair <int,int>
#define fi first
#define se second
#define mpr make_pair
#define pb push_back

void fileio()
{
  #ifdef LGS
  freopen("in.txt","r",stdin);
  freopen("out.txt","w",stdout);
  #endif
}
void termin()
{
  #ifdef LGS
  std::cout<<"\n\nEXECUTION TERMINATED";
  #endif
  exit(0);
}

using namespace std;

const LL MOD=998244353;

LL qpow(LL x,LL a)
{
	LL res=x,ret=1;
	while(a>0)
	{
		if(a&1) (ret*=res)%=MOD;
		a>>=1;
		(res*=res)%=MOD;
	}
	return ret;
}

LL n,m,k,f[10000010],p,fac[10000010],inv[10000010],cval[10000010],mpp[10000010];

int main()
{
  fileio();
  freopen("sanhok.in","r",stdin);
  freopen("sanhok.out","w",stdout);

  fac[0]=1;repn(i,10000005) fac[i]=fac[i-1]*i%MOD;
  inv[10000003]=qpow(fac[10000003],MOD-2);
  for(int i=10000002;i>=0;--i) inv[i]=inv[i+1]*(i+1)%MOD;
  cin>>n>>m>>k;
  p=qpow(m,MOD-2);
  LL bas=(MOD-p)%MOD;
  mpp[0]=1;repn(i,10000005) mpp[i]=mpp[i-1]*bas%MOD;
  
  cval[k]=1;//cval[i]=C(n-i,k-i)
  LL cmul=1;
  for(int i=k-1;i>=0;--i)
  {
    (cmul*=(n-i))%=MOD;
    cval[i]=cmul*inv[k-i]%MOD;
  }
  f[k]=1;
  for(int i=k-1;i>=0;--i)
  {
    f[i]=(f[i+1]+cval[i]*mpp[k-i])%MOD;
    LL add=(f[i+1]-mpp[k-i-1]*cval[i+1]%MOD+MOD)%MOD;
    (add*=(MOD-p))%=MOD;
    (f[i]+=add)%=MOD;
  }

  LL pi=1,mul=1,ans=0;
  rep(i,k+1)
  {
    LL val=pi*qpow(i,k)%MOD*mul%MOD*inv[i]%MOD;
    (pi*=p)%=MOD;(mul*=(n-i))%=MOD;
    (ans+=val*f[i])%=MOD;
  }
  cout<<ans<<endl;

  termin();
}
本文转载于网络 如有侵权请联系删除

相关文章

  • 移动端自动播放视频

    TS(TransportStream,传输流)是一种封装的格式,它的全称为MPEG2-TS。是一种视频格式,一般用于实时流媒体和广播电视领域。Mp4在IOS下可以自动播放,但是在部分安卓机下无法自动播放产生黑屏。Ts可实现自动播放,IOS8以上和Android4.4以上都支持。基于自动播放的优势需要下ffmpeg来将Mp4转化成Ts视频。下面下载操作如下所示:mac下可以运行//安装 brewinstallffmpeg //生成ts视频 ffmpeg-iloop_moon.mp4-fmpegts\ -codec:vmpeg1video-s960x540-b:v1500k-r30-bf0\ -codec:amp2-ar44100-ac1-b:a128k\ loop_moon.ts 还可以控制视频大小(-s),帧速率(-r),视频比特率(-b:v),音频比特率(-b:a),音频通道数(-ac),采样率(-ar)复制推荐使用jsmpeg-player,它是基于jsmpeg封装的npm包npminstall@cycjimmy/jsmpeg-player--save cnpminstall@c

  • 【论文解读】NLP重铸篇之Word2vec

    论文标题:EfficientEstimationofWordRepresentationsinVectorSpace 论文链接:https://arxiv.org/pdf/1301.3781.pdf 复现代码地址:https://github.com/wellinxu/nlp_store/blob/master/papers/word2vec.py 论文标题:word2vecParameterLearningExplained 论文链接:https://arxiv.org/pdf/1411.2738.pdfword2vec原论文讲得比较简单,几乎没有细节,本文会根据另一篇论文【word2vecParameterLearningExplained】,来详细介绍两种加速方法。本文使用python+tensorflow2.0来复现word2vec模型,所以模型中的反向梯度计算与参数优化更新,都是使用的tf中的自动求导与优化器实现,也因此本文中只涉及到word2vec的两种结构(CBOW与Skip-gram)及两种加速方式(Huffman树-层次softmax和负采样)从输入到loss的前向

  • np.random.choice方法

    默认为有放回的抽样(可以重复)np.random.choice(5,3)和np.random.randint(0,5,3)意思相同,表示从[0,5)之间随机以等概率选取3个数np.random.choice(5,3,p=[0.1,0,0.3,0.6,0])表示分别以p=[0.1,0,0.3,0.6,0]的概率从[0,1,2,3,4]这四个数中选取3个数以下为无放回的抽样(不会出现重复的元素)np.random.choice(a=5,size=3,replace=False,p=None)np.random.choice(a=5,size=3,replace=False,p=[0.2,0.1,0.3,0.4,0.0])此方法也可以对列表List类型元素使用aa_milne_arr=['pooh','rabbit','piglet','Christopher']np.random.choice(aa_milne_arr,5,p=[0.5,0.1,0.1,0.3])importnumpyasnp a1=np.r

  • 秒表检定装置秒表检定仪时间检定仪秒表检定设备

    SYN5301型 时间检定仪该款设备结合了秒表检定仪、日差测量仪/校表仪、指针式电秒表检定仪、标准时间间隔发生器等4种功能,采用高稳定度石英晶体振荡器作为时间基准,使用7寸大液晶触摸屏,采用大规模集成电路FPGA技术,全数字控制,实现高精度时间间隔输出,整机具有高稳定度、高准确度的优点,功能完善,操作方便,抗干扰能力强。可供各级计量部门、工厂、院校及各科研单位检定401/405电秒表,407/408电秒表、411数字式毫秒计、415/417/417B型数字式电秒表等时间类仪器。产品概述     SYN5301型时间检定仪是一款高精度时间检定仪。本设备是根据JJG237-2010《秒表检定规程》的要求制作的一款多功能,综合性的时间检定自动测试装置,用于检定机械秒表、电子秒表、指针式电秒表、数字式电秒表、数字式毫秒仪,以及各种计时器等,被测仪器通过测量该标准时间间隔信号,得到被检仪器测量该标准时间间隔信号的实际测量值,从而得到被检仪器测量误差,达到检定的目的,适用于各种类秒表的量值传递,可以建立秒表检定仪标准装置,开展对时间类仪器进行检定/校准。关键词:秒表检定装置,秒表检定仪,时间检定仪

  • 当网红程序员“他二哥”的挡脸贴纸摘下之后

    大家好,我是本号背后最有技术含量的程序员“他二哥”,练习时长两年半,喜欢唱推送技术干货、跳展现鹅厂程序员文化、rap陪大家吃瓜唠嗑。趁最近产品放年假,我用3个需求买通本号运营,终于排到今日的推送广告位官宣出道。先表个态吧,哥能红靠的是脸吗?明明是靠护发的功力和文末的福利。 二哥,你怎么穿着品如的衣服爱我你怕了吗。《护发十二时辰》,带你深入♂了解哥的魅力。你都看到这里了,不给福利那我岂不是渣男。下面有5道数学题,答对1道可获得1个他二哥表情包。 5道题全答对者,请截图5个表情包+本人微信ID发送腾讯技术工程公众号后台,二哥将从5题全对的小聪明中随机抽取38位幸运儿发奖。奖品种类包括罗技鼠标、站立办公架子、防脱洗发水以及鹅厂精美周边(任一)。活动时间:8月13日-8月16日题目 1.有一池荷花,生长的速度是一天增一倍,要20天才能长满整个池塘,请问长满半个池塘要几天?2.科学家在实验室喂养一条虫子,这种虫子生长的速度很快,每天都长长1倍,20天就长到20厘米,问:当它长到5厘米时用了几天?3. 8瓶液体,1瓶有毒,小白鼠喝了毒液体会立刻死亡。至少需要几只小白鼠才能检验出哪个瓶子里有毒药?(

  • R语言日常笔记(4)修改基因最大表达值

    问题描述:差异基因分析中有一些基因会有异常表达,例如说,A基因在大部分样本表达量介于1-10之间,然后A基因在甲样本表达量高达10000以上,这就是明显的异常表达值。对于这一列处理方法: (1)删除异常样本 (2)或者修改其异常表达值下面的代码用于完成第二个方法 rm(list=ls()) setwd('D:\\work\\F1\\mut') load('mRNA_exprSet.Rdata') library(dplyr) library(tidyr) library(tcltk) u<-1:2000 plot.new() pb<-tkProgressBar("进度","已完成%",0,100) for(iin1:nrow(mRNA_exprSet)){ mRNA_exprSet[i,which.max(mRNA_exprSet[i,])]<-NA info<-sprintf("已完成%d%%",round(i*100/nrow(mRNA_e

  • 《大话计算机》之:计算的本质、bio

    根据《大话计算机》内容你点我贴一贴中所述,冬瓜哥收集了“大话存储”和”大话计算机”两个公众号中帖子下的留言如下(蓝色表示往期已回答,红色表示本期选中):计算的本质是什么指令系统我想看分支预测的章节,Intel的漏洞和这个有关fork流程6.5.3中qpi选路原理能贴吗?特别是8p的选路ddr内存初始化浅析和memorytraining介绍内存和MMIO的译码规则和内存在BIOS和OS下的布局情况memorymap和decode这两个概念,特别是decode5.2.3cache组关联7.1.3DMA与缓存的一致性第一章入门部分10.2.1.1用户栈和内核栈10.9.1.29.5.3.30.9.2.410.2.2.36.1.1.超线程并行6.1.2.多核心/多CPU并行计算本质是什么?10.9.1.2讲的是bio数据结构。

  • 5.8 VR扫描:亮风台完成1.2亿元B+轮融资;上海驾校用VR教学,科目二合格率85%

    AR开发商亮风台完成1.2亿元B+轮融资近日,AR开发商亮风台宣布完成1.2亿元B+轮融资,本轮投资方包括MYEGCapital、活水资本等境内外美元和人民币基金,老股东纪源源星资本、美图公司追加。亮风台成立于2012年,自主研发了HiAR技术基础平台、HiLeia通讯平台、AR眼镜HiARGlasses等。亮风台表示,本轮融资将主要用于公司产品和服务的进一步商业化落地。VRPinea独家点评:AR市场正越发火热,AR内容也将越来越多。上海驾校拟将签署1.8亿人民币合同,用于VR教学主营驾考培训业务的东方时尚公告称,拟与合作方签署1.8亿元的合同,购买VR汽车驾驶模拟器设备以及相关的软件授权、系统维护等服务。东方时尚于2017年11月开始投入VR汽车驾驶模拟器,并对无驾驶经验的学员进行教学测试。截至2019年5月7日,东方时尚已共对277人进行了测试,并称平均科目二合格率达到85%。VRPinea独家点评:又降低了一次交补考费的风险……I/O大会:ARCore带来更具交互性、真实感AR体验在今日的I/O大会上,谷歌更新了ARCore,并为用户带来了更具交互性、更具真实感体验的Augme

  • Python的列表学习(四)

    列表的定义很简单,关键字是list,比如我们定义一个列表,它的所有的方法来自list类,我们可以来看下llist类的方法,见如下的代码:#!/usr/bin/envpython #coding:utf-8 list=[1,2,3,4,5] printdir(list) printhelp(type(list))复制见如上代码执行后的输出内容:C:\Python27\python.exeD:/git/Python/FullStack/Study/index.py ['__add__','__class__','__contains__','__delattr__','__delitem__','__delslice__','__doc__','__eq__','__format__','__ge__','__getattribute__','__getitem

  • 多线程实现方式 转

    进程与线程进程是程序在处理机中的一次运行。一个进程既包括其所要执行的指令,也包括了执行指令所需的系统资源,不同进程所占用的系统资源相对独立。所以进程是重量级的任务,它们之间的通信和转换都需要操作系统付出较大的开销。线程是进程中的一个实体,是被系统独立调度和分派的基本单位。线程自己基本上不拥有系统资源,但它可以与同属一个进程的其他线程共享进程所拥有的全部资源。所以线程是轻量级的任务,它们之间的通信和转换只需要较小的系统开销。Java支持多线程编程,因此用Java编写的应用程序可以同时执行多个任务。Java的多线程机制使用起来非常方便,用户只需关注程序细节的实现,而不用担心后台的多任务系统。Java语言里,线程表现为线程类。Thread线程类封装了所有需要的线程操作控制。在设计程序时,必须很清晰地区分开线程对象和运行线程,可以将线程对象看作是运行线程的控制面板。在线程对象里有很多方法来控制一个线程是否运行,睡眠,挂起或停止。线程类是控制线程行为的唯一的手段。一旦一个Java程序启动后,就已经有一个线程在运行。可通过调用Thread.currentThread方法来查看当前运行的是哪一个线程

  • 基于 k8s 的 Jenkins 构建集群实践

    在大型团队的CI构建里具有丰富最佳实践的经验。今天我给大家分享的更多是聚焦在Jenkins本身,结合我在Jenkins实际使用过程中和整个JenkinsSlave管理演化的过程的案例,这样能给大家带来更好的借鉴和参考体验。 下面是主要要分享的四大内容:Jenkins分布式构建架构基于Lable的Slave集群管理基于Docker插件的容器化实践基于Kubernetes的容器化实践一.Jenkins分布式构建架构1.1架构图Jenkins分布式架构一个Master和多个SlaveNode分布式的架构。在JenkinsMaster上管理你的项目,可以把你的一些构建任务分担到不同的SlaveNode上运行,Master的性能就提高了。如果单纯的使用Master去构建,除了要承担项目上的编译、测试等开销外,还会大大的影响Jenkins应用本身占用memory和CPU资源。1.2JenkinsSlave连接方式JenkinsSlave连接方式常使用下面两种:通过SSH启动Slave代理在Jenkins上直接配置,相当于从Master往Slave上连接,从Master上主动发起的请求。通过JNLP

  • 浅谈压缩感知(十九):MP、OMP与施密特正交化

    关于MP、OMP的相关算法与收敛证明,可以参考:http://www.cnblogs.com/AndyJee/p/5047174.html,这里仅简单陈述算法流程及二者的不同之处。 主要内容: MP的算法流程及其MATLAB实现 OMP的算法流程以及MATLAB实现 MP与OMP的区别 施密特正交化与OMP的关系 一、MP(匹配追踪)的算法流程: 二、MP的MATLAB实现: %MP:匹配追踪算法 %dictionary:超完备字典 %x:待表示信号 %M=4;N=10; %Phi=randn(M,N);%字典 %fornn=1:N %Phi(:,nn)=Phi(:,nn)/norm(Phi(:,nn)); %end %b=randn(M,1);%信号 functionx=MP(dictionary,x,iter) [M,N]=size(dictionary); residual=zeros(M,iter);%残差矩阵,保存每次迭代后的残差 residual(:,1)=x;%初始化残差为x L=size(residual,2);%得到残差矩阵的列 pos_num=zeros(1

  • mac 启动apache + php

      一、启动Apache 在终端里输入命令,启动Apache:sudoapachectlstart 关闭Apache:sudoapachectlstop 重启Apache:sudoapachectlrestart 查看Apache版本:httpd-v MacOSX10.9.X中的Apache版本信息: Serverversion:Apache/2.4.16(Unix) Serverbuilt: Jul22201521:03:09 启用Apache之后,在浏览器中访问http://localhost或http://127.0.0.1,如果出现“Itworks!”就表示运行正常。 活在当下,从零出发

  • Iterator

    迭代对于我们搞Java的来说绝对不陌生。我们常常使用JDK提供的迭代接口进行Java集合的迭代。 Iteratoriterator=list.iterator(); while(iterator.hasNext()){ Stringstring=iterator.next(); //dosomething }复制 迭代其实我们可以简单地理解为遍历,是一个标准化遍历各类容器里面的所有对象的方法类,它是一个很典型的设计模式。Iterator模式是用于遍历集合类的标准访问方法。它可以把访问逻辑从不同类型的集合类中抽象出来,从而避免向客户端暴露集合的内部结构。在没有迭代器时我们都是这么进行处理的。如下: 对于数组我们是使用下标来进行处理的: int[]arrays=newint[10]; for(inti=0;i<arrays.length;i++){ inta=arrays[i]; //dosomething }复制 对于ArrayList是这么处理的: List<String>list=newArrayList<String>(); for

  • markdown中设置、调整图片尺寸

    使用百分比描述尺寸 <imgsrc="https://img2018.cnblogs.com/blog/1122471/201902/1122471-20190222185756735-1641099963.png"width="60%"> 复制 使用宽度描述尺寸 <imgsrc="https://img2018.cnblogs.com/blog/1122471/201902/1122471-20190222185756735-1641099963.png"width="600"> 复制 没有尺寸描述 <imgsrc="https://img2018.cnblogs.com/blog/1122471/201902/1122471-20190222185756735-1641099963.png"> 复制 或 ![](https://img2018.cnblogs.com/blog/1122471/201902/1122471-20190222185756735-1641099963.png) 复制

  • py下windows用户安装lxml

    windows用户在安装lxml可能会因为缺少C语言库报错可以选择到UnofficialWindowsBinariesforPythonExtensionPackages下载whl文件例如:使用python3.5版本则下载lxml-3.6.4-cp35-cp35m-win_amd64.whl然后 pipinstallwheel pipinstallf:\lxml-3.6.4-cp35-cp35m-win_amd64.whl(你lxml的whl文件的存放目录)复制 无语言基础,自学python所做的各种笔记,欢迎大牛指点.

  • 机器学习实践中的7种常见错误

    http://ml.posthaven.com/machine-learning-done-wrong http://blog.jobbole.com/70684/     Statisticalmodelingisalotlikeengineering.   Inengineering,therearevariouswaystobuildakey-valuestorage,andeachdesignmakesadifferentsetofassumptionsabouttheusagepattern.Instatisticalmodeling,therearevariousalgorithmstobuildaclassifier,andeachalgorithmmakesadifferentsetofassumptionsaboutthedata.   Whendealingwithsmallamountsofdata,it’sreasonabletotryasmanyalgorithmsaspossibleandtopickthebestonesincethecostof

  • 微信消息推送,获取access_token时AppSecret错误或者access_token无效 invalid credential, access_token is invalid or not latest rid

    最近微信推送消息出现:获取access_token时AppSecret错误或者access_token无效invalidcredential,access_tokenisinvalidornotlatestrid,   这个access_token无效的问题,之前消息推送都是没有问题的, 就最近一周定时器发送消息推送出现偶尔发送成功,偶尔发送提示这个access_token的问题 前提:微信公众号AppId和AppSecret都没有错的情况下,之前都可以 造成这个问题的原因是:微信获取access_token接口调用量/上线次数达到了顶峰10000,如图1所示:   如图1所示,调用接口次数达到上线,导致获取access_token失败的问题; 于是查找code,发现access_token获取居然是没进行全局缓存记录下来,直接每次调用接口获取一次,如下代码所示: ///<summary> ///获取会员微信息 ///</summary> ///<paramname="openid"></param&

  • 常见的4种抓包工具的对比简述

    4种抓包工具的对比 一、httpwatch: 1.   httpwatch与IE和firefox浏览器集成,但不支持chrome;httpwatch界面清晰直观,发送请求后可以快速简单的查看Cookies,Headers,QueryStringsandPOSTdata,能够通过页面分组处理多页面场景。 2.   实时分级时间展示图能够展示一个http/https请求的处理过程;通过不同的颜色展示网络请求计时,如DNS查询,tcp连接;以瀑布形式展示浏览器事件,例如从浏览器渲染和页面加载计时就开始了,可以自动检查性能问题。 3.   安装简单,不需要设置代理和证书;提供接口API可以被大部分编程语言自动化调用、录制、保存结果。 4.   但只能看不能修改 二、Fiddler: 1.Fiddler是一个独立的应用,可以调试PC、Mac或Linux系统和移动设备的之间的通信,支持大部分框架如java、.net、java、Ruby,需要设置代理。 2.能够暂停Http通讯,并

  • 2021icpc西安邀请赛赛旅后游总结

    突然想起来自己已经躺平了一个月(指每天高强度csgo),期末考试+实训完成后回家继续划水了几天,居然忘记把邀请赛的经历写个总结。。。 如果不是昨天打了场cf,怕是要到多校开始之后才回想起来,到那时记忆剩余量肯定几乎见底了(现在大概也是) 先放战利品( 颈椎圣手警告!!!!!!!!!!!!! sakurafubuki继2次区域赛打铁之后,终于在邀请赛拿了个银。滚榜前59,滚完榜后rk七十几还是六十几来着,不记得了,银牌线rk81。 在封榜的1个小时里还是没有把K做出来>﹏<,现场重现: (封榜之后) 队友:K题直接暴力肯定能过 我:不对把这复杂度肯定要O(n)或者带log的 (短暂思考之后) 我:长得像个层次遍历,每次合并把根插到最左边 (造了几个样例(为什么造了几个样例这个做法都没有问题啊真的牛皮)) 队友:确实,就这么写 (wa了6发之后比赛结束,一群人去WC) 旁白(:K题直接并查集暴力就能过xxxxxxxxxxxfjagioavnosdnviosdnfasdfasfasfghllv 我:。。。 队友:。。。 复制 K就这样被完美错过了。。。虽

  • enum class,强类型美剧

    在标准C++中,枚举类型不是类型安全的。枚举类型被视为整数,这使得两种不同的枚举类型之间可以进行比较。 C++11引进了一种特别的"枚举类",可以避免上述的问题。使用enumclass的语法来声明: enumclassresult { success, flase, unknow, };复制 此种枚举为类型安全的。枚举类型不能隐式地转换为整数;也无法与整数数值做比较。  只能进行强转后进行比较 static_cast<int>(result1);复制  

相关推荐

推荐阅读