[AGC043D] Merge Triplets

题目传送门

很有意思的计数题

解法

考虑经过操作后得到的排列的性质


性质1:
p r e ( i ) pre(i) pre(i):前i个位置的最大值,则不会出现超过3个的连续位置的 p r e pre pre相同
必要性
考虑反证,若有超过 3 3 3个的连续位置的 p r e pre pre相同,那么至少有连续有连续三次选择了比第一次选择要小的数,那么至少一个块的长度为 4 4 4,题目中规定块长为 3 3 3,因此不合法
充分性
发现没有充分性,比如: { 2 , 1 , 4 , 3 , 6 , 5 } \{2,1,4,3,6,5\} {2,1,4,3,6,5},手玩模拟一下就会发现有问题
性质2
若排列总长为 3 N 3N 3N, i i i个的连续位置的 p r e pre pre相同的个数为 c n t i cnt_i cnti,那么 c n t 2 ≤ N − c n t 3 cnt_2\le N-cnt_3 cnt2Ncnt3
必要性
对于 c n t 2 cnt_2 cnt2 c n t 3 cnt_3 cnt3来说,他们对应的块内的大小关系是一定的,所以可得 c n t 2 + c n t 3 ≤ N cnt_2+cnt_3\le N cnt2+cnt3N,移项就行了
我们可以化简:
c n t 2 ≤ N − c n t 3 ⇒ 3 c n t 2 ≤ 3 N − 3 c n t 3 ⇒ 3 c n t 2 ≤ ( c n t 1 + 2 c n t 2 + 3 c n t 3 ) − 3 c n t 3 ⇒ 移项得 c n t 2 ≤ c n t 1 \begin{aligned} &cnt_2\le N-cnt_3\\ \Rightarrow&3cnt_2\le 3N-3cnt_3\\ \Rightarrow&3cnt_2\le (cnt_1+2cnt_2+3cnt_3)-3cnt_3\\ \Rightarrow^{移项得}&cnt_2\le cnt_1 \end{aligned} 移项得cnt2Ncnt33cnt23N3cnt33cnt2(cnt1+2cnt2+3cnt3)3cnt3cnt2cnt1

最后我们发现性质1性质2加起来就有了充分性


状态设计:

f i , j : 前 i 个数, c n t 1 − c n t 2 = j 的方案数 f_{i,j}:前i个数,cnt_1-cnt_2=j的方案数 fi,j:i个数,cnt1cnt2=j的方案数
显然 a n s = ∑ k = 0 3 n f 3 n , k ans=\sum_{k=0}^{3n} f_{3n,k} ans=k=03nf3n,k

状态转移:

考虑从小到大放数,对放 1 / 2 / 3 1/2/3 1/2/3个数分别考虑
f i , j → f i + 1 , j + 1 f i , j → f i + 2 , j − 1 ∗ ( i − 1 ) f i , j → f i + 3 , j ∗ ( i − 1 ) ∗ ( i − 2 ) \begin{aligned} &f_{i,j}\to f_{i+1,j+1}\\ &f_{i,j}\to f_{i+2,j-1}*(i-1)\\ &f_{i,j}\to f_{i+3,j}*(i-1)*(i-2) \end{aligned} fi,jfi+1j+1fi,jfi+2,j1(i1)fi,jfi+3j(i1)(i2)
就好了

code:

#include<bits/stdc++.h>
using namespace std;
const int N = 2e3 + 7, M = N * 3;
typedef long long ll;
int n,mod,ans;
int f[M][M<<1];
int ad(int x,int y){ return (1ll*x+1ll*y)%mod; }
void work(int i,int j){f[i+1][j+1+M]=ad(f[i+1][j+1+M],f[i][j+M]);f[i+2][j-1+M]=ad(f[i+2][j-1+M],1ll*f[i][j+M]*(i+1)%mod);f[i+3][j+M]=ad(f[i+3][j+M],1ll*f[i][j+M]*(i+1)%mod*(i+2)%mod);
}
int main() {scanf("%d%d",&n,&mod); n=n*3;f[0][M]=1;for(int i=0;i<n;i++) for(int j=-i;j<=i;j++) work(i,j);for(int i=0;i<=n;i++) ans=ad(ans,f[n][i+M]);printf("%d\n",ans);
}

TXL

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/119601.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

使用Docker配置深度学习的运行环境

文章目录 推荐实验环境前言docker安装docker操作docker配置常见方法&#xff08;安装包、联网、程序管理器&#xff09;安装驱动的前提要求传统方法安装驱动程序程序管理器安装联网安装deb包安装 安装完成后的设置非传统方法安装-通过容器安装驱动的前提要求安装NVIDIA-Contain…

基于Django的博客管理系统

1、克隆仓库https://gitee.com/lylinux/DjangoBlog.git 若失效&#xff1a;https://gitee.com/usutdzxy/DjangoBlog.git 2、环境安装 pip install -Ur requirements.txt3、修改djangoblog/setting.py 修改数据库配置&#xff0c;其他的步骤就按照官方文档。 DATABASES {def…

在 Amazon 搭建无代码可视化的数据分析和建模平台

现代企业常常会有利用数据分析和机器学习帮助解决业务痛点的需求。如制造业中&#xff0c;利用设备采集上来的数据做预测性维护&#xff0c;质量控制&#xff1b;在零售业中&#xff0c;利用客户端端采集的数据做渠道转化率分析&#xff0c;个性化推荐等。 亚马逊云科技开发者…

低代码赋能| 绿色智慧矿山解决方案

在世界能源日趋紧张的背景下&#xff0c;能源产业的数字化升级是大势所趋。矿山行业作为国家能源安全的“压舱石”&#xff0c;也必须进行产业升级。一直以来&#xff0c;国家都在大力推动智慧矿山建设。通过大数据、GIS、物联网、云计算、人工智能等新兴技术&#xff0c;实现矿…

R语言图形的组合( par(),layout(),par(fig()) )

引入d.class进行画图 > d.class<-read.csv("D://class.csv",header T) > attach(d.class) > opar<-par(no.readonly TRUE)非常简单的数据&#xff0c;需要可自取 链接&#xff1a;https://pan.baidu.com/s/1zNx5z9JsaaRqFueRgGY3mQ 提取码&#x…

微信小程序新版隐私协议弹窗实现最新版

1. 微信小程序又双叒叕更新了 2023.08.22更新&#xff1a; 以下指南中涉及的 getPrivacySetting、onNeedPrivacyAuthorization、requirePrivacyAuthorize 等接口目前可以正常接入调试。调试说明&#xff1a; 在 2023年9月15号之前&#xff0c;在 app.json 中配置 __usePriva…

Vite打包性能优化及填坑

最近在使用 Vite4.0 构建一个中型前端项目的过程中&#xff0c;遇到了一些坑&#xff0c;也做了一些项目在构建生产环境时的优化&#xff0c;在这里做一个记录&#xff0c;以便后期查阅。(完整配置在后面) 上面是dist文件夹的截图&#xff0c;里面的内容已经有30mb了&#xff…

Revit SDK:SpatialFieldGradient 在面上显示渐变颜色(AVF)分析显示样式

前言 这个例子使用Revit显示样式功能将面显示成不同的颜色。分析显示样式参考官方文档。 内容 效果&#xff1a; 核心逻辑&#xff1a; 得到一个 SpatialFieldManager拾取一系列的面&#xff1a;uiDoc.Selection.PickObjects(ObjectType.Face)计算面上的 UV 值&#xff0c;…

COSCon'23 开源市集:共赴一场草坪上的开源派对

一年一度的开源盛会&#xff0c;第八届中国开源年会&#xff08;COSCon23 &#xff09;&#xff0c;将于10月28~29日&#xff0c;在四川成都市高新区菁蓉汇召开&#xff01;本次大会的主题是&#xff1a;“开源&#xff1a;川流不息、山海相映”&#xff01; 我们预期会有超过1…

更健康舒适更科技的照明体验!SUKER书客护眼台灯 L1上手体验

低价又好用的护眼台灯是多数人的需求&#xff0c;很多人只追求功能性护眼台灯&#xff0c;显色高、无频闪、无蓝光等基础需求。但是在较低价格中很难面面俱到&#xff0c;然而刚发布的SUKER书客L1护眼台灯却是一款不可多得的性价比护眼台灯&#xff0c;拥有高品质光源&#xff…

第63步 深度学习图像识别:多分类建模误判病例分析(Tensorflow)

基于WIN10的64位系统演示 一、写在前面 上两期我们基于TensorFlow和Pytorch环境做了图像识别的多分类任务建模。这一期我们做误判病例分析&#xff0c;分两节介绍&#xff0c;分别基于TensorFlow和Pytorch环境的建模和分析。 本期以健康组、肺结核组、COVID-19组、细菌性&am…

mp代码生成插件

mp代码生成插件 1.下载下面的插件 2.连接测试 3.生成代码的配置 4.生成代码 红色的是刚刚生成的。 我觉得不如官方的那个好用&#xff0c;唯一的好处就是勾选的选项能够看的懂得。

视频云存储/安防监控/AI视频智能分析网关V3:工服检测功能详解

在一些工地、后厨、化工、电力等特定的场景中&#xff0c;工服的穿戴是必不可少的。这不仅是安全制度的要求&#xff0c;更能降低工作风险、提高工作效率。TSINGSEE青犀AI 边缘计算网关硬件 —— 智能分析网关可以通过实时监测和识别工人的工装穿戴情况&#xff0c;确保他们符合…

什么是接口测试,如何做接口测试?

比起点点点的功能测试&#xff0c;“接口测试”显得专业又高大上&#xff0c;也因此让有些初级测试人员“望而生畏”。别担心&#xff0c;其实接口测试也是功能测试的一种&#xff0c;它是针对接口进行的功能测试。 写在前面&#xff1a;本文参考了茹炳晟老师的《测试工程师 全…

软件架构设计(三) B/S架构风格-层次架构(一)

层次架构风格从之前的两层C/S到三层C/S,然后演化为三层B/S架构,三层B/S架构之后仍然在往后面演化,我们来看一下层次架构演化过程中都有了哪些演化的架构风格呢? 而我们先简单了解一下之前的层次架构风格中分层的各个层次的作用。 表现层:由于用户进行交互,比如MVC,MVP,…

医院小程序如何在线搭建?实战解析

在当今数字化时代&#xff0c;移动应用程序成为我们生活中必不可少的一部分。特别是在医疗领域&#xff0c;移动应用程序的需求更为迫切。为了满足这一需求&#xff0c;开发一个医疗小程序成为了许多医疗机构的优先选择。 在本文中&#xff0c;我们将分享一个实战攻略&#xff…

大数据可视化大屏实战项目(3)图书销售展示全国地图可视化---HTML+CSS+JS【源码在文末】(可用于比赛项目或者作业参考中)

大数据可视化大屏实战项目&#xff08;3&#xff09;图书销售展示全国地图可视化---HTMLCSSJS【源码在文末】&#xff08;可用于比赛项目或者作业参考中&#x1f415;&#x1f415;&#x1f415;&#xff09; 一&#xff0c;项目概览 ☞☞☞☞☞☞项目演示链接&#xff1a;http…

实力认证!OceanBase获“鼎信杯”优秀技术支撑奖

6 月 30 日&#xff0c;2023 “鼎信杯”信息技术发展论坛在京隆重举办第二届“鼎信杯”大赛颁奖典礼。OceanBase 凭借完全自主研发的原生分布式数据库&#xff0c;以及丰富的核心系统国产数据库升级案例&#xff0c;斩获“优秀技术支撑奖”。 论坛上&#xff0c;国内首个基于在…

打车系统网约车系统开发支持APP公众号H5小程序版本源码

一、操作流程 二、业务模式 三、用户端 用户注册登录&#xff1a;未注册的手机号将自动创建账号 通过好友的邀请链接进行注册&#xff0c;将会绑定上下级关系 也可以注册的时候输入好友的邀请码&#xff0c;也可以绑定关系 用户充值&#xff1a; 用户下单支付时&#xff0c;可以…

【大数据】数据湖:下一代大数据的发展趋势

数据湖&#xff1a;下一代大数据的发展趋势 1.数据湖技术产生的背景1.1 离线大数据平台&#xff08;第一代&#xff09;1.2 Lambda 架构1.3 Lambda 架构的痛点1.4 Kappa 架构1.5 Kappa 架构的痛点1.6 大数据架构痛点总结1.7 实时数仓建设需求 2.数据湖助力于解决数据仓库痛点问…