Codeforces 1034E

题意

给你两个 $2^n$ 的数组 $a_0,..,a_{2^n-1}$ 和 $b_0,..,b_{2^n-1}$

在模 $4$ 意义下求子集卷积

$n\le 21$

H. Playing games

题意

你有 $n$ 堆石子，数量分别是 $a_1,..,a_n$

问最多能选出几堆使得玩 Nim游戏 满足后手必胜

$n,a_i\le 5*10^5$

LOJ #2340

题意

有 $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

题意

给你两个数组 $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$

NOIP 之后就写了这么个 simple 题

BZOJ 4589

题意

你有 $n$ 堆有序的石子，每堆的数量都是 $\le m$ 的一个质数

你要玩 Nim游戏，问有多少种方案先手必败

$n\le 10^9, m\le 5*10^4$

LOJ #2269

题意

你有一棵$n$个点的树，点$y$有一个$[0,m)$内的整数权值$a_u$

定义一棵树的权值是点权的异或和

有$q$次操作

• Change x y，表示把第$x$个点的权值改成$y$

• Query x，表示询问有多少个非空的联通子树的权值是$x$，模$10007$

$n,q\le30000,m\le128$

LOJ #2127

题意

你有一个数字 $0$，每秒你会以 $p_i$ 的概率选择 $i$，$i\in[0,2^n-1]$，和自己的数进行按位或，问期望多少秒后数字变成 $2^n-1$

$n\le20,\sum p_i=1$

Codeforces 662C

题意

给出一个$n$行$m$列的$01$矩阵，可以任意次取反一行或一列，最小化矩阵中$1$的总数

$n\le20,m\le10^5$