首页 > 其他分享 >YC278A [ 20240420 CQYC省选模拟赛 T1 ] 作画(paint)

YC278A [ 20240420 CQYC省选模拟赛 T1 ] 作画(paint)

时间:2024-04-30 17:12:30浏览次数:29  
标签:10 省选 YC278A T1 paint 20240420

题意

给定排列 \(S\),最初 \(S_i = i\)。

每次进行以下操作,进行 \(t\) 次。

  • 选择下标 \(i, j\),使得 \(S_i = S_j\)。

求进行 \(t\) 次后,\(S\) 有至少 \(k\) 种数字的概率。

\(n \le 10, t \le 10 ^ {18}\)。

Sol

考虑概率转方案,变为有多少种方案使得最终状态有 \(k\) 种数字。

不难注意到我们并不关心每个位置到底是哪些数。

我们只关心每种数到底有多少个。

考虑一种状态,\(f_i\) 表示第 \(i\) 种颜色的个数。

因为我们不关心具体的颜色,因此可以让 \(f\) 满足偏序关系。

注意到总状态数非常少,对于 \(n = 10\) 时,总状态数只有 \(42\) 种。

直接上矩阵快速幂转移即可。

标签:10,省选,YC278A,T1,paint,20240420
From: https://www.cnblogs.com/cxqghzj/p/18168372

相关文章

  • 【C】---- T1:英寸转厘米
    题目需要一个把英寸单位转换为厘米单位(1英寸=2.54厘米)的程序。编程#include<stdio.h>intmain(void){floatinch;//定义英寸值变量floatcm;//定义厘米值变量scanf("%f",&inch);//输入英寸值cm=inch*2.54;//英寸转换厘米printf("......
  • web server apache tomcat11-24-Virtual Hosting and Tomcat
    前言整理这个官方翻译的系列,原因是网上大部分的tomcat版本比较旧,此版本为v11最新的版本。开源项目从零手写实现tomcatminicat别称【嗅虎】心有猛虎,轻嗅蔷薇。系列文章webserverapachetomcat11-01-官方文档入门介绍webserverapachetomcat11-02-setup启动web......
  • web server apache tomcat11-22-logging 日志
    前言整理这个官方翻译的系列,原因是网上大部分的tomcat版本比较旧,此版本为v11最新的版本。开源项目从零手写实现tomcatminicat别称【嗅虎】心有猛虎,轻嗅蔷薇。系列文章webserverapachetomcat11-01-官方文档入门介绍webserverapachetomcat11-02-setup启动web......
  • 联合省选2024 做题总结
    D1T1季风心梗题。设\(sx_i=\sum\limits_{j\lei}x_j\),\(sy_i\)同理。枚举\(r=m\bmodn\),设\(m=p\cdotn+r\),那么当\(|x-(p\cdotsx_n+sx_r)|+|y-(p\cdotsy_n+sy_r)|\)不超过\((p\cdotn+r)k\),一定存在合法的方案,即解关于\(p\)的绝对值不等式:\[|x-(p\cdotsx_n+sx_r......
  • 照亮数学的七道光芒 T1-4
    照亮数学的七道光芒勇气对于第\(k\)次攻击,其攻击力为:\[a_k=\frac{x^{2^k}}{2^{2^k-2}}\]对于这个题,显然就是找最小的\(k\)使满足这个式子\[\frac{x^{2^k}}{2^{2^k-2}}\geq2^n\]以\(2\)为底取对数,有\[2^k\log_2x-(2^k-2)≥n\]\[2^k≥\frac{n-2}{\log_2x-1}\]如......
  • web server apache tomcat11-21-monitor and management 监控与管理
    前言整理这个官方翻译的系列,原因是网上大部分的tomcat版本比较旧,此版本为v11最新的版本。开源项目从零手写实现tomcatminicat别称【嗅虎】心有猛虎,轻嗅蔷薇。系列文章webserverapachetomcat11-01-官方文档入门介绍webserverapachetomcat11-02-setup启动web......
  • web server apache tomcat11-16-mbean
    前言整理这个官方翻译的系列,原因是网上大部分的tomcat版本比较旧,此版本为v11最新的版本。开源项目从零手写实现tomcatminicat别称【嗅虎】心有猛虎,轻嗅蔷薇。系列文章webserverapachetomcat11-01-官方文档入门介绍webserverapachetomcat11-02-setup启动web......
  • web server apache tomcat11-14-CGI
    前言整理这个官方翻译的系列,原因是网上大部分的tomcat版本比较旧,此版本为v11最新的版本。开源项目从零手写实现tomcatminicat别称【嗅虎】心有猛虎,轻嗅蔷薇。系列文章webserverapachetomcat11-01-官方文档入门介绍webserverapachetomcat11-02-setup启动web......
  • 痞子衡嵌入式:在i.MXRT1xxx系列上用NAND型启动设备时可用两级设计缩短启动时间
    大家好,我是痞子衡,是正经搞技术的痞子。今天痞子衡给大家分享的是在i.MXRT1xxx系列上用NAND型启动设备时可用两级设计缩短启动时间。去年痞子衡写过一篇骚操作文章《借助i.MXRT10xx系列INIT_VTOR功能可以缩短程序热重启时间》,这对于NAND型启动设备上程序热重启时间的......
  • web server apache tomcat11-12-SSL/TLS Configuration
    前言整理这个官方翻译的系列,原因是网上大部分的tomcat版本比较旧,此版本为v11最新的版本。开源项目从零手写实现tomcatminicat别称【嗅虎】心有猛虎,轻嗅蔷薇。系列文章webserverapachetomcat11-01-官方文档入门介绍webserverapachetomcat11-02-setup启动web......