「Codeforces 1046B」Hyperspace Highways
Read more题意
给你一张 $n$ 个点 $m$ 条边的无向图，每个点有点权，$q$ 次操作
C a w，将第 $a$ 个点的权值改为 $w$A a b，询问 $a$ 到 $b$ 所有可能的简单路径上的点权最小值
简单路径即不经过一个点超过一次的路径
$n,m,q\le 10^5$
「Codeforces 1046B」Hyperspace Highways
Read more给你一张 $n$ 个点 $m$ 条边的无向图，每个点有点权，$q$ 次操作
C a w，将第 $a$ 个点的权值改为 $w$
A a b，询问 $a$ 到 $b$ 所有可能的简单路径上的点权最小值
简单路径即不经过一个点超过一次的路径
$n,m,q\le 10^5$
给定 $n$ 次多项式 $F(x)$，求 $G(x)$ 满足
$$
G(x)\equiv
\left(\left(1+\ln\left(2+F(x)-F(0)-\exp\left(\int\frac{1}{\sqrt{F(x)}}\right)\right)\right)^k\right)’ \pmod{x^n}
$$
保证常数项是模 $998244353$ 的二次剩余。
注意 $\pm\sqrt{F(x)}$ 均为合法解，你只需要输出 $\sqrt{F(x)}$，舍去 $-\sqrt{F(x)}$，我们认为两个解中常数项较小的解为 $\sqrt{F(x)}$。
所有运算在模 $998244353$ 意义下进行。
当存在某个 $x$，式子 $x^2\equiv a\pmod p$ 成立时，称“$a$ 是模 $p$ 的二次剩余(Quadratic residue)”
有 $n$ 座城市，第 $i$ 座城市的人口是 $w_i$，有一些无向边。
现在城市被划分为了若干个州，每个州至少包含一个城市，每个城市恰好在一个州内。
设 $V_i$ 是第 $i$ 个州的城市集合。
定义一条道路是一个州的内部道路，当且仅当这条道路的两个端点城市都在这个州内。如果一个州内部存在一条起点终点相同，不经过任何不属于这个州的城市，且经过这个州的所有内部道路都恰好一次并且经过这个州的所有城市至少一次的路径（路径长度可以为 $0$），则称这个州是不合法的。
定义第 $i$ 个州的满意度为：第 $i$ 个州的人口在前 $i$ 个州的人口中所占比例的 $p$ 次幂，即：
$$\left(\frac{\sum_{x\in V_i}w_x}{\sum_{j=1}^i\sum_{x\in V_j}w_x}\right)^p$$
定义一个划分的满意度为所有州的满意度的乘积。
求所有合法的划分方案的满意度之和。
答案对 $998244353$ 取模。
$n\le 21,0\le p\le 2$
时限 $10s$
「HDU 6057」Kanade's convolution
给你两个数组 $A[0\dotsc 2^m-1]$ 和 $B[0 \dotsc 2^m-1]$
你需要计算
$$C[k]=\sum_{i{\rm and}j=k}A[i{\rm xor}j]\times B[i{\rm or}j]$$
输出 $\sum_{i=0}^{2^m-1}C[i]\times 1526^i \bmod 998244353$
$m\le 19$
NOIP2018 唯一没做出来的题
要是写完两题后直接去打暴力大概也不止50分吧
反正确实跪在这题了
你有一个 $n$ 行 $m$ 列的矩阵，左上角为 $(0,0)$
每一个位置有一个数字 $0/1$
你需要从 $(0,0)$ 走到 $(n-1,m-1)$，只能向右或向下走 $(R/D)$，一共 $n+m-2$ 步，这会形成一条路径
把方向记下来可以得到同样长度的只包含 $R/D$ 的字符串 $w(P)$
并且经过的 $n+m-1$ 个位置的数字连起来可以得到一个 $01$ 串 $s(P)$
你需要求出有多少种填数的方案，使得对于任意两条路径 $P_1,P_2$，若 $w(P_1)>w(P_2)$，那么 $s(P_1)\le s(P_2)$
模 $10^9+7$
$n\le 8,m\le 10^6$
平面上有$n$个圆，编号$1..n$
重复如下操作直到不存在圆
选择一个半径最大的圆，如果有多个，选择编号最小的
把所有与第1步选出的圆有交的圆删除
其中两个圆有交当且仅当存在一个点，这个点同时被两个圆包含，包含定义为点在圆内或者圆上
$n\le 3*10^5$
你有一张 $n$ 个点 $m$ 条边的无向图，你需要选择三个互不相同的点 $s,c,f$
询问有多少种选择的方案使得存在至少一条从 $s$ 出发经过 $c$ 到达 $f$ 的简单路径（不经过重复点）
$n\le 10^5,m\le 2*10^5$