首页 > 其他分享 >UOJ #514. 【UR #19】通用测评号

UOJ #514. 【UR #19】通用测评号

时间:2024-04-04 20:22:25浏览次数:22  
标签:kMod geq 概率 19 加数 UR int 管道 UOJ

Description

有 \(n\) 个管道,每个管道的最大大小为 \(a\),每次等概率随机选一个没满的管道里放一个石子,当所有管道的大小都 \(\geq b\) 时停止,问装满的管道的期望个数,与 \(998244353\) 取模。

\(1 \le n \le 250,1 \le b < a \le 250\)。

Solution

先考虑一个引理:有 \(n\) 个集合,有一些集合不能加数,那么对于所有能加数的集合,它是下一个被加数的集合的概率刚好等于所有集合都能加数,且它是原本所有能加数的集合中第一个加数的概率。这个很好证。

所以原题就可以转化为每次随便加石子,最终所有的管道的大小都 \(\geq b\) 时大小 \(\geq a\) 的期望个数。

不妨先求 \(1\) 号管道被装满的概率,最终答案就是这个概率\(\times n\)。

由于操作序列是无法确定长度的,所以不好求概率。考虑利用引理,定义一个管道不能再加石子当且仅当它是 \(1\) 号且 \(\geq a\) 或者不是 \(1\) 号且 \(\geq b\)。

这样的话操作序列长就是 \((n-1)\times b+a\) 了,然后只要用 \(1\) 减去最后一步是 \(1\) 号管道的概率。

不妨设 \(t_i\) 表示 \(i\) 最后一次操作的时间(\(1\leq t_1<t_2<\dots<t_{n-1}<(n-1)\times b+a\)),则最后一步是 \(1\) 的概率即为:

\[\frac{\prod_{i=1}^{n-1}{\binom{t_i-1-(i-1)b}{b-1}}}{\prod_{i=1}^{n-1}{(n-i+1)^{t_{i}-t_{i-1}}}} \]

上面那个是总的方案数,下面是选择每个位置要乘的概率。

然后对这个进行 dp 即可,设 \(f_{i,j}\) 表示当前在时间 \(i\),有 \(j\) 个非 \(1\) 管道被填满的概率,则 \(f_{i+1,j}\leftarrow \frac{f_{i,j}}{n-j},f_{i+1,j+1}\leftarrow \frac{f_{i,j}\times \binom{i-j\cdot b}{b-1}}{n-j}\)。

最终答案就是 \(n\times \left(1-(n-1)!\times f_{(n-1)b+a-1,n-1}\right)\)。

时间复杂度:\(O(n^2b+na)\)。

Code

#include <bits/stdc++.h>

// #define int int64_t

const int kMaxN = 255, kMaxS = 9e4 + 5, kMod = 998244353;

int n, a, b;
int fac[kMaxS], ifac[kMaxS], inv[kMaxS], f[kMaxS][kMaxN];

constexpr int qpow(int bs, int64_t idx = kMod - 2) {
  int ret = 1;
  for (; idx; idx >>= 1, bs = (int64_t)bs * bs % kMod)
    if (idx & 1)
      ret = (int64_t)ret * bs % kMod;
  return ret;
}

inline int add(int x, int y) { return (x + y >= kMod ? x + y - kMod : x + y); }
inline int sub(int x, int y) { return (x >= y ? x - y : x - y + kMod); }
inline void inc(int &x, int y) { (x += y) >= kMod ? x -= kMod : x; }
inline void dec(int &x, int y) { (x -= y) < 0 ? x += kMod : x; }

int C(int m, int n) {
  if (m < n || m < 0 || n < 0) return 0;
  return 1ll * fac[m] * ifac[n] % kMod * ifac[m - n] % kMod;
}

void prework() {
  fac[0] = ifac[0] = fac[1] = ifac[1] = inv[1] = 1;
  for (int i = 2; i <= n * a; ++i) {
    inv[i] = 1ll * (kMod - kMod / i) * inv[kMod % i] % kMod;
    fac[i] = 1ll * i * fac[i - 1] % kMod;
    ifac[i] = 1ll * inv[i] * ifac[i - 1] % kMod;
  }
}

void dickdreamer() {
  std::cin >> n >> a >> b;
  prework();
  int m = (n - 1) * b + a;
  f[0][0] = 1;
  for (int i = 0; i < m; ++i) {
    for (int j = 0; j <= std::min(n - 1, i / b); ++j) {
      int p = 1ll * f[i][j] * inv[n - j] % kMod;
      inc(f[i + 1][j], p), inc(f[i + 1][j + 1], 1ll * p * C(i - j * b, b - 1) % kMod);
    }
  }
  std::cout << 1ll * n * sub(1, 1ll * f[m - 1][n - 1] * fac[n - 1] % kMod) % kMod << '\n';
}

int32_t main() {
#ifdef ORZXKR
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
#endif
  std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
  int T = 1;
  // std::cin >> T;
  while (T--) dickdreamer();
  // std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
  return 0;
}

标签:kMod,geq,概率,19,加数,UR,int,管道,UOJ
From: https://www.cnblogs.com/Scarab/p/18114553

相关文章

  • vulhub中Apache Solr 远程命令执行漏洞复现(CVE-2019-0193)
    ApacheSolr是一个开源的搜索服务器。Solr使用Java语言开发,主要基于HTTP和ApacheLucene实现。此次漏洞出现在ApacheSolr的DataImportHandler,该模块是一个可选但常用的模块,用于从数据库和其他源中提取数据。它具有一个功能,其中所有的DIH配置都可以通过外部请求的dataC......
  • Delving into Sample Loss Curve to Embrace Noisy and Imbalanced Data
    这篇论文:提出了prob-and-allocate训练策略,在prob阶段获得样本损失,在allocate阶段分配样本权重。以[2]的meta-weight-net为Baseline,取名为CurveNet,进行部分改动。另外,这篇论文提供的源码结构混乱,复现难度较大。主要的工作也是基于meta-weight-net,创新的内容有限。但是,这篇文章......
  • Python+requests+Pytest+logging+allure+pymysql框架详解
    一、框架目录结构1)tools目录用来放公共方法存储,如发送接口以及读取测试数据的方法,响应断言数据库断言前置sql等方法;2)datas目录用例存储接口用例的测试数据,我是用excel来存储的数据,文件数据图片数据等;3)testcases目录用来存放测试用例,一个python文件对应一个接口模块的......
  • Allure测试报告
    allure安装Mac安装方式1brewinstallallure2pipinstallallure-pytestWindows安装方式1https://github.com/allure-framework/allure2/releases2下载解压后将allure.bat添加进系统环境变量中3pipinstallallure-pytestallure特性分析  allure运行   ......
  • 每日一题: 2192. 有向无环图中一个节点的所有祖先
    给你一个正整数 n ,它表示一个 有向无环图 中节点的数目,节点编号为 0 到 n-1 (包括两者)。给你一个二维整数数组 edges ,其中 edges[i]=[fromi,toi] 表示图中一条从 fromi 到 toi 的单向边。请你返回一个数组 answer,其中 answer[i]是第 i 个节点的所有 祖......
  • ctfshow--web12 glob和show_source命令执行
    查看源代码有提示以为是cmd命令解过输入linux命令愣是没反应后来输入phpinfo()才有回显原来是被误导了。一开始想的是直接写入一句话木马点击查看代码@eval($_POST['attack']);echo111;//这里的echo111是方便看我们有没有植入成功的这里有111的回显证明木马注入成......
  • scRNAtoolVis包使用:UMAP, featureplot,heatmap美化
    参考原文链接:https://mp.weixin.qq.com/s/K8FHv0dxriaGxKI0efRN5ghttps://mp.weixin.qq.com/s/gtnYWJcUubNKT4SIldk9uQ1.安装devtools::install_github('junjunlab/scRNAtoolVis')library(scRNAtoolVis)#过程报错,需要首先安装依赖包:magickinstall.packages("magick"......
  • Rust Thread Adventure
    HelloeveryoneandwelcometothewonderfulworldofRustMultithreading!Today,we'regoingtoexplorethisexcitingareatogether.Areyouready?Buckleupandlet'sgo!InRust,threadsarelikethesuperheroesofyourprogram.Theycanperfo......
  • When Rubber Meets the Road: Unveiling the Curious Case of Volvo Truck Engine Fai
    Buckleup,folks!Today,we'retakingajoyrideintotheworldofVolvotruckengine.Holdontoyourseats,asweexplorethefascinatingreasonsbehindtheseunexpectedbreakdowns.Andhey,don'tworry,we'vegottheultimatediagnosticto......
  • SpringSecurity认证和授权流程详解
    什么是SpringSecuritySpringSecurity是一个Java框架,用于保护应用程序的安全性。它提供了一套全面的安全解决方案,包括身份验证、授权、防止攻击等功能。SpringSecurity基于过滤器链的概念,可以轻松地集成到任何基于Spring的应用程序中。它支持多种身份验证选项和授权策略,开发人员......