本文章用于记录菜鸡 CXY07 做到的一些有趣的题目。
链接尽量丢 Luogu 的，统一起来。
由于文章太长了，所以改成索引。
给定一个 n×m 的 01 矩阵，现在可以无限次对某一行或一列的每个数字取反，求最少的 1 的个数。
n≤20 , m≤105
有一个 n×n 的正方形，每行每列都恰好有一个 1，计算有多少子正方形满足每行每列恰好有一个 1。
n≤105
给定长度为 n 的序列 ai，元素两两不相等，等概率随机选一个非空子集 bi。有另一人知道 a 来猜测 b，每次可以询问一个 ak，若在 b 中无此数字，则告知“无”，否则告知 b 中所有满足 akmmodp 的数（m 为任意正整数）
现每次一定用最优方法猜测，问猜完 b 所有数字的期望次数 ×(2n−1)
n≤5000,p≤108，p 为素数或 qk （q 是素数，k 为一正整数）
给定三个长度为 n 的排列 {ai},{bi},{ci}，问有多少对 (x,y) 满足 ax<ay,bx<by,cx<cy
n≤5×106
给定一棵 n 个点，以 1 为根的树，现让你对边染色 (0/1) 。有 m 条限制，每条限制形如 (ui,vi) ，意为 ui 到 vi 的路径上至少要有一条 1 边，其中保证 ui 是 vi 的祖先。问染色方案数。
n,m≤5×105
在一条长度为 B 的线段 l 上，等距离截取一些点（包括左右端点），令点数为 n，相邻两个端点间距离为 d (d≤D)。每个端点处都作一条长度为 H 的线段垂直于 l。相邻线段之间都存在一条全等的抛物线，抛物线总长为 L，令其最低点与 l 的距离为 h。给定 D,H,B,L，求在 n 最小时 h 的值。
满足 B≤L
开始手上有数字 0 ，每秒按照一定概率选择一个 [0,2n−1] 之内的数字，将手上的数字或上他。问手上的数变成 2n−1 的期望秒数。
n≤20，满足 ∑pi=1
给出 n 个物品，每个物品有一个权值 wi。
定义一个集合 S 的权值为 W(S)=∣S∣∑x∈Swx，对于一个集合的划分，定义其权值为 W′(R)=∑S∈RW(S)。
求所有将 n 个物品分为 k 个集合的方案的权值和。
n,k≤2×105,wi≤109
给定数组 ai，定义 f(i,j)=∣∑p=ijap∣，称数组的美丽度为 max{f(i,j)}(i≤j)。每次给定一个 x，m 次询问，每次询问在将整个数组加上 x 的基础上的美丽度。询问相互独立。
n≤2×105。
给定正整数 n,A,B，定义 a 为一个排列中前缀 max 的个数，b 为这个排列中后缀 max 的个数。求长度为 n 的排列中，满足 a=A,b=B 的排列有多少个。答案对 998244353 取模。
n≤105,0≤A,B≤n。
交互题。
给定 n，则一开始有集合 S={x∣x≤n,x∈N+}，其中有一个特殊值 x，你需要通过以下操作找到他。
A a：询问集合 S 中 a 的倍数个数 (1≤a≤n)。
B a：先询问集合 S 中 a 的倍数个数，然后删去所有还在 S 中的 a 的倍数，而 x 不会被删去 (2≤a≤n)。
C a：回答 x=a。
A,B,C 操作的个数和不能超过 10000。
1≤x≤n≤105。
给定 n 个数 ai，每次可以将其中一个 +1 或者 -1。求最少多少次操作可以让整个序列的 gcd>1。
n≤105,ai≤1012。
有 n 个人，第 i 个人年龄为 ai，两个人 i,j 是朋友当且仅当 ai AND aj=0。现在这 n 个人要加入传销组织，组织会给他们金币。
主动加入的不会得到金币。
一个人 i 若在组织内，则可以邀请不在组织内的朋友 j 加入，并得到 ai 的金币。一个人只能被邀请一次。
问 n 个人最多得到多少金币。
n,ai≤2×105。
给定长度为 n 的序列 ai，每次可以选择连续的两个数字 ax,ax+1，删去他们，再将 −(ax+ax+1) 插入回原位置。
现在进行 n−1 次操作，求最后剩下的数字的最大值。
1≤n≤2×105,−109≤ai≤109。
现有一个 n 行无限列的矩阵，每行从左往右有三个点 bi,wi,ri，分别是蓝点、白点、红点。
Alice 可以将蓝点/蓝点和白点向右移动 k 格，Bob 可以将红点/红点和白点向左移动 k 格，不允许改变蓝白红点的相对位置，k 是质数或两个质数的乘积，但是有一个值 d 不能使用。无法操作者输。问先手必胜还是必败。
n≤105,−105≤bi<wi<ri≤105。
给定 n,k，需要建出 k 个有相同外接圆的正 ai 边形，其中 3≤ai≤106 且 ai 两两不同。
可以旋转任意正多边形，如果多个正多边形与外接圆的交点重合，则只算与外接圆有一个交点。现问最少与外接圆有多少交点。
3≤n≤106,1≤k≤n−2。
给定一个长度为 n 的数组 a，现在可以做最多 n 次操作，每次选取三个不同的下标 i,j,k，将 ai,aj,ak 都变为 ai⊕aj⊕ak，其中 ⊕ 是异或。求一种方案使得所有数字都相等，或判断不可能。
3≤n≤105,1≤ai≤109。
给定一个长度为 n 的数组 a，求长度至少为 3，且满足 al⊕ar=∑i=l+1r−1ai 的子区间 [l,r] 的数量，其中 ⊕ 是异或。
3≤n≤2×105,1≤ai<230。
交互题。
给定一棵深度为 h 的满二叉树，则其恰好有 2h−1 个节点。你可以进行以下询问不超过 n+420 次：
选择三个互不相同的点 u,v,w，交互库将回答以 w 为根的时候，u,v 的 lca。
你需要回答原树的根。
3≤h≤18。
给定长度分别为 n,m 的序列 a,b，随机取两个下标 x,y，定义其 k 次价值为 (ax+by)k。
求对于 i∈[1,t]，一次游戏的 i 次价值的期望分别是多少。
1≤n,m,≤105,mod=998244353。
给定长度为 n 的非负整数序列 {an}，定义一个子序列 {bi} 是优秀的，当且仅当：bi<bi+1,∀i=j abiandabj=0。
一个优秀子序列的价值为 φ(1+∑abi)，求所有优秀子序列的价值和。
1≤n≤106, 0≤ai≤2×105。
给定一棵 n 个节点的树，和一个初始为空的点对的集合 S，有 m 次操作，需要支持 4 种操作：
- 断开一条边，再加入另一条边（保证仍然是树）。
- 在点对集合 S 中加入点对 (x,y)。
- 在点对集合 S 中删除第 i 个加入的点对。
- 给定 (x,y)，询问若把集合中的点对看做树上路径，集合中所有路径是不是都经过边 (x,y)。
1≤n≤105, 1≤m≤3×105，任何时刻 ∣S∣≤10。
T 组询问，每次给出长度为 m 的序列 a。
现在你将生成一个随机序列，字符集为 1−n，每次在序列末尾等概率随机一个数。当 a 成为了随机序列中的一个连续子序列则结束随机。
询问随机序列的期望长度。
1≤T≤50,1≤n,m≤105。
给定 x,y,k。
求分数 yx 的个数满足：1≤x≤n,1≤y≤m,gcd(x,y)=1，且在 k 进制下 yx 是纯循环小数（或者整数）。
1≤n≤109, 1≤m≤109, 1≤k≤2×103。