0%

Description

一个初始为 0 的二进制数,有 mm 次操作。

ii 次操作是将这个二进制数加上 2ai2^{a_i} 。这个操作以 pip_i 的概率执行。

如果某次操作执行了并且修改了二进制数的 kk 位,那么它会带来 kk 的代价。

问代价和的期望,答案对 998244353998244353 取模。

n=maxai105,m2×105n=\max a_i\leqslant10^5, m\leqslant2\times10^5

阅读全文 »

Description

一棵 nn 个结点的树。初始时 aabb 是黑的,其他点是白的。

每次可以把某个黑点染成红的并把与它相邻的白点染成黑的。

问把结点染红的顺序有多少种。

1a,bn2345671\leqslant a,b\leqslant n\leqslant234567

答案对 998244353998244353 取模,时限 10s 。

阅读全文 »

Description

令 d(i) 表示 ii 的约数个数。

i=1Aj=1Bk=1Cd(ijk)\sum_{i=1}^A\sum_{j=1}^B\sum_{k=1}^Cd(ijk)

A,B,C105A,B,C\leqslant10^5

阅读全文 »

Description

有一列数 aia_i ,有 QQ 个操作:

  1. 对于某个 ii ,以 pp 的概率使 aia_i 减一(若 ai=0a_i=0 则忽略);
  2. 指定某些 aia_i ,从这些 aia_i 中的所有大于零的位置随机选一个,对于每个 aia_i 你需要求出选到它的概率。

你还要求出每个 aia_i 执行完所有操作后的期望。

CC 为 2 操作的数量:

n200,Q2×105,C103;n\leqslant200,Q\leqslant2\times10^5,C\leqslant10^3; 初始时 ai100a_i\leqslant100

时限 6s 。

阅读全文 »

Description

平面上有一个直线导轨,和 nn 个挡板(线段)。现在你可以在直线导轨上的某个位置放置一个长度为 LL 的激光发射器;它会以垂直于导轨的方向(向两边)发射激光。激光打到挡板上时会被吸收。

挡板间不相交,挡板和导轨不相交;挡板所在直线和导轨夹角不超过 8585^\circ

最大化吸收到激光的挡板总长。(只计算被激光照到的部分;计算这部分的挡板长度而不是激光宽度)

n104,L2×109n\leqslant10^4, L\leqslant2\times10^9 ,所有坐标绝对值 109\leqslant10^9

多组数据,数据组数 T100T\leqslant100 ,时限 10s 。

阅读全文 »

Description

一个 nn 个点 mm 条边的无向连通图,qq 次询问。每次询问给出一个集合 SS ,问有多少结点 xx 满足:

  1. x∉Sx\not\in S;
  2. 删除结点 xx 及与其相连的所有边之后, SS 中的点不连通。

n,q105;m,S2×105n,q\leqslant10^5;m,\sum|S|\leqslant2\times10^5

多组数据,数组组数 T10T\leqslant10 ;时限 10s10s

阅读全文 »

Description

有一个非负整数 xx 。你要执行 mm 次操作,每次操作是 x = randint(0, x)= 表示赋值, randint(0, x) 均匀随机地在 [0,x][0, x] 中取一个整数)。

现在已知初始的 xx 会随机在 [0,n][0, n] 取值,且取 ii 的概率是 pip_i ,求最后取到 [0,n][0, n] 每个数的概率。

n105,m1018n\leqslant10^5, m\leqslant10^{18}

阅读全文 »