Codeforces 1671 F Permutation Counting 题解

题目链接

\(p_i>p_{i+1}\)的位置个数称为间隔数

首先想到一个暴力做法。从小到大挨个添加1-n中的每个数,注意到添加数i时,只能添加到当前序列的最后11个位置中,否则逆序对数就会超。令\(dp_{i,j,p,msk}\)表示当前添加到数i,当前逆序对数为j,间隔数为p,msk是一个集合表示当前序列最后11个位置中哪些满足\(p_i>p_{i+1}\)。转移比较简单。但是这个dp的第一维是n,但n很大。矩阵快速幂也是不行的,后面的维度也很大。

我们考虑把一个长度为n的排列分段。令\(mx_i\)表示\(max_{j=1}^i p_j\)。我们找到从左往右第一个满足\(mx_i=i\)的位置,也就是第一个满足\(p_1\cdots p_i\)是一个排列的位置,然后把1-i分为一段,数组剩下的部分统一减i,然后不断进行同样的分段操作直到序列用完。发现分出的每一段都是一个"小的排列",且左侧的一个小排列中的所有\(p_i\)都小于右侧任意一个小排列中的\(p_i\)。注意到两个段之间不会贡献任何的逆序对数或间隔数,所以排列p的逆序对数和间隔数等于每一小段内部的逆序对数和间隔数之和。

一个小段的长度如果>12,那它的逆序对数就>11,所以此时的p肯定不合法。证明:令小段为一个1-k的排列\(b_1\cdots b_k\),其前缀max为\(c_1\cdots c_k\)。对于任意\(1\le i<k\),满足\(b_i<c_i\)。我们从左往右一个个加入\(b_i\),当加入到i(\(1\le i <k\))时,如果还有满足\(x<b_i\)的x没被加入,那肯定能至少形成一个还没被统计的逆序对;如果不存在这样的x,那肯定存在一个j满足\(j<i,b_j>b_i\)且加入j时有不止一个这样的x,我们现在加入i只是消耗了加入j时产生的一个逆序对而已。综上,总的逆序对个数一定会\(\ge k-1\)。因此我们可以用一个简单的背包算出数组\(f_{i,j,p}\)表示长度为i,逆序对数为j,间隔数为p的小段个数。为了保证对于任意\(1\le i<k\)满足\(b_i<c_i\),dp的时候需要状压一下。

算出f数组之后为了得到n的答案,可能会想到多项式快速幂什么的,其实根本不需要多项式技巧。注意到小段的长度\(>1\)时,逆序对数和间隔数都不为0;而小段长度为1时这两个值都为0。所以长度>1的小段个数\(\le 11\),再做一次背包,然后用插板法把其他长度为1的小段插进去即可。

没仔细算时间复杂度,反正不高。

点击查看代码
#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 pdd pair <double,double>
#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 t,n,k,x,dp[4100][20][20][20];//dp[msk][k][x][lst]
LL dp2[20][30][20][20];//dp2[cnt][lensum][k][x]

LL rinv[100];
LL C(LL nn,LL mm)
{
  LL ret=1;for(LL i=nn;i>=nn-mm+1;--i) (ret*=i)%=MOD;
  repn(i,mm) (ret*=rinv[i])%=MOD;
  return ret;
}

int main()
{
  fileio();

  rep(i,95) rinv[i]=qpow(i,MOD-2);
  LL lim=12;
  dp[0][0][0][0]=1;
  rep(msk,1<<lim) rep(kk,lim) rep(xx,lim) rep(lst,lim) if(dp[msk][kk][xx][lst])
  {
    LL sz=__builtin_popcount(msk);
    if(msk==(1<<sz)-1&&msk>0) continue;
    LL val=dp[msk][kk][xx][lst],addk=0;
    for(int nxt=lim-1;nxt>=0;--nxt)
    {
      if(msk&(1<<nxt)) ++addk;
      else if(kk+addk<=11) (dp[msk|(1<<nxt)][kk+addk][xx+(int)(lst>nxt)][nxt]+=val)%=MOD;
    }
  }
  rep(i,1<<lim) rep(kk,lim) rep(xx,lim) repn(lst,lim) (dp[i][kk][xx][0]+=dp[i][kk][xx][lst])%=MOD;
  dp2[0][0][0][0]=1;
  rep(i,lim) rep(j,25) rep(kk,lim) rep(xx,lim) if(dp2[i][j][kk][xx])
  {
    LL val=dp2[i][j][kk][xx];
    for(int nxtlen=2;nxtlen<=lim&&j+nxtlen<=24;++nxtlen) rep(kkk,lim-kk) rep(xxx,lim-xx)
    {
      LL msk=(1<<nxtlen)-1;
      if(dp[msk][kkk][xxx][0]==0) continue;
      (dp2[i+1][j+nxtlen][kk+kkk][xx+xxx]+=val*dp[msk][kkk][xxx][0])%=MOD;
    }
  }

  cin>>t;
  rep(tn,t)
  {
    cin>>n>>k>>x;
    LL ans=0;
    rep(cnt,k+1) for(int sz=cnt+cnt;sz<=24;++sz)
    {
      LL val=dp2[cnt][sz][k][x];
      if(val==0||sz>n) continue;
      LL tot=n-sz,spas=cnt+1;
      LL mul=C(tot+spas-1,spas-1);
      (ans+=val*mul)%=MOD;
    }
    cout<<ans<<endl;
  }

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

相关文章

  • 树莓派连接驱动板控制舵机

    硬件16路PWMServo舵机驱动板模块PCA9685树莓派MG90S9g舵机连接GND->RPiGNDSCL->RPiSCL1SDA->RPiSDA1VCC->RPi3.3VV+->RPi5VVCC引脚只是为芯片供电,如果要连接舵机或者LED灯,就使用V+引脚供电,V+引脚支持3.3~6V的电源(芯片的安全电压时5V)。建议通过电源接线柱外接电源供电。 大多数的舵机设计电压都是在5~6V,尤其在多个舵机同时运行时,跟需要有大功率的电源供电。demo#coding:utf-8 #导入__future__文件的division是为了精确除法。 from__future__importdivision importtime #导入Adafruit_PCA9685模块,需要安装 importAdafruit_PCA9685 #使用默认地址(0x40)初始化PCA9685。 #把Adafruit_PCA9685.PCA9685()引用地址赋给PWM标签 pwm=Adafruit_PCA9685.PCA9685() #或者指定不同的地址和/或总线: #pwm=

  • NetCore项目发布对前端项目进行打包合并发布

    在某个小项目中,api使用asp.netcore3.x编写,UI页面则使用Vuejs.正常情况下,项目右键的发布只会发布api项目,而不会管Vuejs的项目. 所以通过简单的改造,在发布该项目时不光发布api本身,同时也编译和发布Vuejs写的页面.这样子就可以2个项目一起部署了. 当然我们也可以通过CI/CD来解决问题.项目结构: *.Manager是一个asp.netcore3.x的webapi项目,主要为ui提供接口. ClientApp目录下时Vuejs的前端UI项目. ClientApp\dist是vuejs在build时的目标文件夹,记得在.gitignore里面排除,这样vuejsbuild的产物就不用提交到版本控制了.Api项目的配置更改点:Startup增加SPA配置//Startup.ConfigureServices services.AddSpaStaticFiles(configuration=> { configuration.RootPath="ClientApp"; }); //Startup.Configure app.Use

  • PCA综合指南

    介绍机器学习中最受追捧且同样令人困惑的方法之一是主成分分析(PCA)。无论我们在不应对PCA复杂性的情况下建立模型的意愿如何,我们都无法长期远离它。PCA的优点在于其实用性。在本文中,首先,我们将直观地了解什么是PCA,如何完成以及其目的。发布后,我们将深入研究PCA背后的数学:线性代数运算,PCA的原理,含义及其应用。[图片上传失败...(image-a48337-1609686500170)]目录信噪比(SNR)维度诅咒逐步进行PCA的方法通过PCA改善SNR线性代数运算奇异值分解的示例降维可变约简因子加载以及如何选择变量PCA可以应用于各种数据吗?讲故事的时间让我们先问一下您想听哪个广播电台?我喜欢听104.8FM(是的!播放爱情歌曲的电台..![图片上传失败...(image-4e886f-1609686500176)]好吧,所以现在一旦我们以104.8的频率调谐到FM,我们就能获得我们选择的广播电台。此外,如果您有注意,如果我们以稍高的频率(例如105或104.5的较低频率)调谐FM,我们仍然可以听到广播电台的声音,但是,当我们离开104.8的频率时,会发生一些情况。。pca

  • vuejs中的组件以及父子组件间通信传值

    (您有任何疑问,都可以进行提问,我们一起探讨)前言您将在本文当中了解到,往网页中添加数据,从传统的dom操作过渡到数据层操作,实现同一个目标,两种不同的方式.以及什么是组件,如何定义和使用组件,父子组件之间如何进行简单的通信传值...对于vuejs,我也只是个初学者,很多人都觉得简单,但我觉得是它并不容易的,就像JQuery的,常用的API也就那些,但是遇到一些炫酷的效果,就是写不来。在切换到写Vuejs代码中,你不需要去关注dom层操作,更多的精力是放在处理数据上,数据是什么,就让页面显示什么,操作数据,就是在操做view(视图),这与JQuery是不一样的,编程思路是需要进行转化的单纯的vuejs其实是不足以撼动jQuery的地位的,它的强大之处在于它的生态系统非常丰富,路由,模型,UI组件等各个部分的钩子等令vuejs风靡国内外,借鉴了Angular中指令,React中组件化等,上手相对而言比较容易如今jQuery时代真是江河日下了,这里我并不是说它不重要,它仍然是非常优秀而重要的,只是任何技术都有辉煌和落幕的时候,时代在进步,技术也在不断更新迭代..从github上的star数

  • 乳腺癌的免疫浸润模式及其临床意义(IF:11.048)

    今天解读的这篇文章发表在PLoSMedicine(最新影响因子11.048)上,题目为PatternsofImmuneInfiltrationinBreastCancerandTheirClinicalImplications:AGene-Expression-BasedRetrospectiveStudy。虽然发表在2016年,但是这篇文章在免疫方面的研究十分细致和深入,很值得大家学习和借鉴。背景乳腺肿瘤的免疫浸润与临床结局有关。但是,过去的工作并未说明组成免疫应答的细胞类型的功能差异。这项研究的目的是确定乳腺肿瘤中免疫浸润的细胞组成差异是否会影响生存和治疗反应,以及这些效应是否因分子亚型而异。方法和结果作者将建立的计算方法(CIBERSORT)应用于将近11,000个肿瘤的整体基因表达谱中,以推断免疫细胞的22个子集的比例。进而研究了每种细胞类型与存活率和对化学试剂的反应之间的关联,将细胞比例建模为四分位数。作者发现,根据雌激素受体(ER)状态,几乎没有免疫浸润的肿瘤与不同的生存模式相关。在ER阴性样本中,缺乏免疫浸润的肿瘤预后最差,而在ER阳性疾病中,它们与中间的预后相关。在研究

  • django 实现文件下载功能

    一、概述在实际的项目中很多时候需要用到下载功能,如导excel、pdf或者文件下载,当然你可以使用web服务自己搭建可以用于下载的资源服务器,如nginx,这里我们主要介绍django中的文件下载。前端实现方式a标签+响应头信息<a href="/download/1/">下载图片</a>复制注意:这里的1指的是MySQL表的主键id后端实现方式使用django有三种文件下载方式,分别是HttpResponse,StreamingHttpResponse,FileResponse详情,请参考链接https://www.jb51.net/article/137790.htm本文主要介绍StreamingHttpResponse实现方式二、实际操作新建项目新建一个Django项目untitled1,这里的是Django2.x版本。目录结构如下:./ ├── app │   ├── admin.py │   ├── apps.py │   ├── __init__.py │   ├── migrations │   │   └── __init__

  • 使用OpenCV和Python构建运动热图视频

    作者|RobertoSannazzaro来源|Medium编辑|代码医生团队介绍:OpenCV(或称为“开源计算机视觉”)是英特尔于1999年开发的一个库,主要针对计算机视觉和实时视频操作,它使用C++编写,但受不同语言(包括Python)的支持。工作流程:该程序基于一种称为高斯背景减法的技术。该技术广泛用于用稳定的相机检测运动物体。背景减法会创建一个代表帧背景(图像的静态部分)的蒙版,并且对于每个帧,它都会减去前一个。对该算法如何工作的两个主要步骤进行简要概述:背景初始化:在第一步中,通过冻结第一帧来计算背景模型。更新:在第二步中,将从前一帧减去下一帧,因此如果两个帧之间发生更改(移动),则这些帧的差异将反映出该更改,可以通过应用过滤器来进行市场销售。以下是背景遮罩应用于从城市摄像机录制的短视频的示例:代码:对于整个项目存储库,请在此处检查。https://github.com/robertosannazzaro/motion-heatmap-opencv/blob/master/README.md该代码通过读取输入视频文件并初始化所需的一些变量开始:capture=cv2.Vide

  • Zabbix3.4.8搭建及邮件微信告警实现

    安装参考文档:https://www.zabbix.com/documentation/3.4/zh/manual/installation/install_from_packages配置:主机ip操作系统zabbix版本mysql版本zabbix-server172.27.9.63Centos7.3.1611zabbix_server(Zabbix)3.4.85.7.21zabbix-agent172.27.9.65Centos7.3.1611zabbix_agentd(daemon)(Zabbix)3.4.8/server端:1.安装源码库配置部署包这个部署包包含了yum配置文件:[root@zabbix-server ~]#  rpm -ivh http://repo.zabbix.com/zabbix/3.4/rhel/7/x86_64/zabbix-release-3.4-2.el7.noarch.rpm复制2.安装Zabbix-server部署包[root@zabbix-server ~]# yum -y install zabbix-server-mysql zabbix

  • 【使用攻略】之【地标识别】-快速接入小程序

    致所有开发者: 我们是开发者不是程序员。开发者是最具活力的创新者,是勤恳的践行者,是敏捷的困难解决者,是胸怀梦想,不忘初心的又具有开发能力的一群人。 前期准备百度云账号(有账号请忽略注册)https://passport.baidu.com/v2/?reg创建一个图像识别应用(已创建请忽略)https://console.bce.baidu.com/ai/?fromai=1#/ai/imagerecognition/overview/index创建一个微信小程序账号(有账号请忽略注册)https://mp.weixin.qq.com/cgi-bin/registermidpage?action=index&lang=zh_CN&token=微信小程序开发工具安装https://developers.weixin.qq.com/miniprogram/dev/quickstart/basic/getstart.html#安装开发工具创建应用获取相关信息应用名称名字方便自己区分应用使用即可,注意查看是否勾选地标识别应用描述简述一下应用场景即可获取应用相关信息AppID、AP

  • python 函数式编程 map reduce

    Python内建了map()和reduce()函数。如果你读过Google的那篇大名鼎鼎的论文“MapReduce:SimplifiedDataProcessingonLargeClusters”,你就能大概明白map/reduce的概念。我们先看map。map()函数接收两个参数,一个是函数,一个是Iterable,map将传入的函数依次作用到序列的每个元素,并把结果作为新的Iterator返回。举例说明,比如我们有一个函数f(x)=x2,要把这个函数作用在一个list[1,2,3,4,5,6,7,8,9]上,就可以用map()实现如下:f(x)=x*x │ │ ┌───┬───┬───┬───┼───┬───┬───┬───┐ │││││││││ ▼▼▼▼▼▼▼▼▼ [123456789] │││││││││ │││││││││ ▼▼▼▼▼▼▼▼▼ [149162536496481]复制现在,我们用Python代码实现:>>>deff(x): ...returnx*x ... >>>r=map(f,[1,2,3,4,5,6,7,8,9])

  • matlab画心形曲线_笛卡尔心形曲线方程

    MATLAB心形曲线基本知识clc;指令可以清除屏幕,所以你可以通过clc指令来清理屏幕clc复制holdon;指令可以将画的图连起来holdon复制clear;清除之前所留的定义clear复制笛卡尔爱心曲线ezpolar('1-sin(t)')复制a=1; theta=0:0.01:2*pi; r=a*(1-sin(theta)); polar(theta,r,'-r');复制特别定制第一种实现方式clear t=-pi:pi/100:pi; r=abs(t); x=r.*sin(t); y=r.*cos(t); plot(x,y) title('Iloveyou.') axisequal复制方法二:gridon可以加上网格,可以通过删除下面代码中的gridon删除表格clear x=-2:0.01:2; y=sqrt(2*sqrt(x.^2)-x.^2); z=asin(abs(x)-1)-pi./2;plot(x,y); gridon; holdon; plot(x,z); axisequal;复制fill语句填色cl

  • Java多线程之内存模型

    目录 多线程需要解决的问题 线程之间的通信 线程之间的同步 Java内存模型 内存间的交互操作 指令屏障 happens-before规则 指令重排序 从源程序到字节指令的重排序 as-if-serial语义 程序顺序规则 顺序一致性模型 顺序一致性模型特性 顺序一致性模型特性 当程序未正确同步会发生什么 参考资料 多线程需要解决的问题 在多线程编程中,线程之间如何通信和同步是一个必须解决的问题: 线程之间的通信: 线程之间有两种通信的方式:消息传递和共享内存 共享内存:线程之间共享程序的公共状态,通过读——写修改公共状态进行隐式通信。如上面代码中的num和Lock可以被理解为公共状态 消息传递:线程之间没有公共状态,必须通过发送消息来进行显示通信 在java中,线程是通过共享内存来完成线程之间的通信 线程之间的同步: 同步指程序中永固空值不同线程间的操作发生的相对顺序的机制 共享内存:同步是显示进行的,程序员需要指定某个方法或者某段代码需要在线程之间互斥执行。如上面代码中的Lock加锁和解锁之间的代码块,或者被synchronized包围的代码块 消

  • 曾子杀彘

    曾子之妻之市,其子随之而泣。 其母曰:“女还,顾反为女杀彘。” 妻子适市来,曾子欲捕彘杀之。 妻止之曰:“特与婴儿戏耳。” 曾子曰:“婴儿非与戏也。婴儿非有智也,待父母而学者也,听父母之教。今子欺之,是教子欺也。母欺子,子而不信其母,非所以成教也。” 遂烹彘也。

  • jenkins

    https://www.jenkins.io/zh/doc/   https://www.w3cschool.cn/jenkins/  

  • b站如何一次性取关10人

    在当前页面控制台输入 $(".be-dropdown-item:contains('取消关注')").click() 复制 出现如下提示 刷新即可 本文来自博客园,作者:泥烟,CSDN同名,转载请注明原文链接:https://www.cnblogs.com/Knight02/p/16653337.html

  • 视频信息查看,帧信息查看

    1、查看视频流index的方法:   方法一、ffprobe/Users/laa/Desktop/abc/视频.mp4 ffprobe-select_streams0-show_packets/Users/laa/Desktop/abc/shipin.mp4|grepflags=   方法二、通过-show_streams参数可以查看到多媒体文件中的流信息,流的信息使用STREAMS标签括起来,可以看到 index=0 codec_name=h264复制 输入命令:ffprobe-show_streams/Users/lily/Desktop/白雾/只有一个关键帧.mp4输出如下: ffprobeversion3.4.2Copyright(c)2007-2018theFFmpegdevelopers builtwithAppleLLVMversion9.0.0(clang-900.0.39.2) configuration:--prefix=/usr/local/Cellar/ffmpeg/3.4.2--enable-shared--enable-p

  • P2822 组合数问题

    题面:https://www.luogu.org/problem/P2822 本题直接将c[i][j]%k=1的(i,j)用前缀和数组记录下来,然后求前缀和即可. 注意:ans[i][j]=ans[i-1][j]+ans[i][j-1]-ans[i-1][j-1] Code: #include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<cstdlib> #include<algorithm> #include<ctime> usingnamespacestd; constintN=2010,M=2005; longlongt,k,n,m,i,j,f[N][N],a[N][N],ans[N][N]; intmain(){ cin>>t>>k; for(i=0;i<=M;i++){ a[i][0]=1; a[i][i]=1; } for(i=1;i<=M;i

  • 【转】H5调用照相机等设备

    使用input标签type值为file,可以调用系统默认的照相机、相册、摄像机、录音功能: <inputtype="file"accept="image/*"capture="camera"> 复制   <inputtype="file"accept="video/*"capture="camcorder"> 复制   <inputtype="file"accept="audio/*"capture="microphone"> 复制    属性说明 accept 打开的系统文件目录 capture 系统所捕获的默认设备,camera:照相机;camcorder:摄像机;microphone:录音; multiple 多选,multiple优先级高于capture,<inputtype="file"accept="image/*"multiple> 测试发现存在很多兼容性问题,下面将测试出的部分结果列出: 设备安卓IOS camera 相机、图库、文件管理器等混合选择项 相机

  • CSS预处理器SASS将迁移到Dart Sass

    所以 node-sass可以换成dart-sass复制 为什么重写Sass? Sass的主要实现有RubySass11和LibSass20(node-sass底层使用的是LibSass),它们都有各自的优缺点。RubySass的实现语言是高级语言Ruby,更容易迭代,但存在运行速度慢,不易安装的缺点。LibSass虽然速度快,但它的开发语言是C/C++,迭代速度慢,无法快速地添加各种功能。复制 为什么使用Dart? Dart的运行速度是真的快,对于大型样式文件,DartSass的处理速度是RubySass的5~10倍,且只比LibSass慢1.5倍左右。同时,Dart是一门具备静态类型的动态语言,对比C/C++甚至是Ruby,Dart相对更容易上手且代码也更易于编写和维护。此外,Dart具备编译输出为JavaScript的能力,使得DartSass可以兼容NodeJS平台。复制 各种实现的后续规划? LibSass作为目前性能最好的Sass实现,后续将继续维护,只是它不再需要背负快速添加各种新功能的压力。RubySass目前也会同步维护,但在无人接手的情况下,它将逐渐边缘化

  • mvc 整体请求流程

       

  • ACM春季集训图论NOIP杂题

    题目传送门:https://www.luogu.com.cn/problem/P3916       #include<iostream> #include<bits/stdc++.h> usingnamespacestd; constintmaxn=100010; intn,m,a[maxn]; vector<int>g[maxn]; voiddfs(intx,intd){ if(a[x])return; a[x]=d; for(inti=0;i<g[x].size();i++){ dfs(g[x][i],d); } } intmain(){ intu,v; cin>>n>>m; for(inti=1;i<=m;i++){ cin>>u>>v; g[v].push_back(u);//反向存储 } for(inti=n;i;i--) dfs(i,i); for(inti=1;i<=n;i++) printf("%d",a[i]); cout<&

相关推荐

推荐阅读