GYM 102978 | XXI Opencup GP of Tokyo
2021/4/13 18:55:52
本文主要是介绍GYM 102978 | XXI Opencup GP of Tokyo,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
A
子题意:在 \(n \times m\) 的网格中,每个格子中的数在 \([0, K]\) 之间,且左小于等于右,上小于等于下,求方案数。
思路:对每个 \(i\),都可以画出一条从左下角到右上角的分界线,一一对应进行往左往下,然后用LGV引理列式子,行列式可能还可以化简。
B
题意:有长度为 \(n\) 的 01 序列,每次可以将相邻两位合并为 & 或 |,求最终合并为 1 的方案数。
思路:注意到只有 0 和 1,枚举所有情况,重述每次合并的过程。
G
对于什么样的 K,能直接求出在模意义下的单位复数根?
首先要满足 \(K | P - 1\),其次就是要求
\[g ^ {0 \frac{P - 1}{K}}, g ^ {1 \frac{P - 1}{K}}, ..., g ^ {(K - 1) \frac{P - 1}{K}} \]互不相等。
否则的话,就要考虑扩域,把一个数记为若干个复数的和,维护每一项系数。在最后求值的时候,用实数运算暴力求出复数,取实部。
这题对于 \(P = 998244353, K = 7\),可以直接取七次单位复根,看到别人代码的瞬间血压直接拉满。
Python快速幂取模:import math, pow(a, b, P)
H
题意:给定 \(n\) 个数 \(a_1, a_2, ..., a_n\) 和 \(m\) 个数 \(b_1, b_2, ..., b_m\),每次有 \(\frac{x}{sum}\) 的概率取出 \(x\),问期望多少次取出 \(a\) 中的所有数。
\(n \le 100\)
\(a_i \le 100\)
\(sum(a) + sum(b) < 998244353\)
反思:
min_max容斥之后的期望我仍然不会算。
应该用期望的线性性质展开。
期望:
- 定义
- 线性性质
- DP
- 解方程
这篇关于GYM 102978 | XXI Opencup GP of Tokyo的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升