GYM 102978 | XXI Opencup GP of Tokyo

本文主要是介绍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\)，其次就是要求

互不相等。

否则的话，就要考虑扩域，把一个数记为若干个复数的和，维护每一项系数。在最后求值的时候，用实数运算暴力求出复数，取实部。

这题对于 \(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的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！