BzhH

很明显是一道高斯消元解线性异或方程组。 对于一个 n×mn\times mn×m 的矩阵,我们给每个点编一个号, 对于第 iii行,第 jjj 列的点,则有 p=(i−1)×m+jp=(i-1)\times m+jp=(i−1)×m+j。 那么与它相邻的点的编号就出来了, 分别是 p1=p−m,p2=p+m,p3=p−1,p4=p+1p_1=p-m,p_2=p+m,p_3=p-1,p_4=p+1p1​=p−m,p2​=p+m,p3​=p−1,p4​=p+1。 那么对于每一个点,我们都可以列出一个方程式 xp⊕xp1⊕xp2⊕xp3⊕xp4=0x_p\oplus x_{p_1}\oplus x_{p_2}\oplus x_{p_3}\oplus x_{p_4}=0 xp​⊕xp1​​⊕xp2​​⊕xp3​​⊕xp4​​=0 那么 n×mn\times mn×m 的矩阵就一共有 nmnmnm 个点,即我们需要列出一个 nmnmnm 元一次方程式组, 那这个方程组求出来的解就一定是答案吗? 不是,很明显,矩阵全部都为0也是这个方程组的一组合法解, 但题目又说了不能全为0,并且保证有解,那么就 ...

[NOIP2007 提高组] 树网的核 [SDOI2011]消防(这一道是上一道的数据加强版) 题意:给定一棵树,找出一条长度小于s的路径,使得该树上的结点到这条路径的最大值最小 首先根据树的直径的定义,对于任意一条路径,距离其最远的点一定在树的直径的端点上. 为了方便求得答案,不妨假设路径就在树的直径上,只需要求出一条路径在树的直径内使得端点到该路径的距离最小 但是有一些特殊情况,比如路径的端点就是树的直径的端点,所以我们还需要求出树上其他点非直径的点到树的直径上的点的最大距离 代码实现,直接用两边dfs求出树的直径,然后维护一下树的直径的前缀和,在树的直径上维护一个单调队列,每次更新答案 代码 #include<iostream>#include<cstdio>using namespace std;const int N = 3e5 + 5;int cnt, d[N], dis[N], sum[N], q1[N], q2[N];int f1[N], f2[N], len, p1[N], p2[N], root, dim[N];int head[N], ve ...

很久之前学过这个东西，但因为一直没有用过就忘记了，写篇博客复习了一下 例题高斯消元解线性方程组 给定义个 nnn 元一次方程组,求出它的解 我们将方程组的系数矩阵表示出来,那么就是 ∣a1,1 a1,2 ... a1,nb1a2,1 a2,2 ... a2,n b2⋮   ⋱   ⋮an,1 an,2 ... an,n bn∣\begin{vmatrix}a_{1,1}~a_{1,2}~...~a_{1,n} b_1\\a_{2,1}~a_{2,2}~...~a_{2,n}~b_2\\\vdots~~~\ddots~~~\vdots\\a_{n,1}~a_{n,2}~...~a_{n,n}~b_n\\\end{vmatrix} ​a1,1​ a1,2​ ... a1,n​b1​a2,1​ a2,2​ ... a2,n​ b2​⋮   ⋱   ⋮an,1​ an,2​ ... an,n​ bn​​​ 对于这个矩阵,我们可以进行下面几种操作 1.把某一行乘以一个非0的数 2.交换某两行 3.把某一行的若干倍加到另一行上 高斯消元则是通过这些操作,将一个系数矩阵变成三角形的形状 首先枚举每一 ...

快速傅里叶变换:在 O(nlog(n))O(nlog(n))O(nlog(n)) 内求出两个多项式的卷积 ###前置知识 ####多项式的点表示法 对于任意一个多项式 A(x)=a0+a1x1+a2x2+a3x3+...+anxnA(x)=a_0+a_1x^1+a_2x^2+a_3x^3+...+a_nx^nA(x)=a0​+a1​x1+a2​x2+a3​x3+...+an​xn,我们都可用 n+1n+1n+1 个点将它表示出来 *** 证明 *** 任取 n+1n+1n+1 个点 (x0,A(x0)),(x1,A(x1)),(x2,A(x2))...(xn,A(xn))(x_0,A(x_0)),(x_1,A(x_1)),(x_2,A(x_2))...(x_n,A(x_n))(x0​,A(x0​)),(x1​,A(x1​)),(x2​,A(x2​))...(xn​,A(xn​)),将它代入多项式可得 {a0+a1x0+a2x02+...+anx0n=A(x0)a0+a1x1+a2x12+...+anx1n=A(x1)...a0+a1xn+a2xn2+...+anxnn=A(xn)\be ...

思路并不难的一道题，实现起来有点麻烦 很明显，时间具有可二分性，对于一个时间t，若时间t内军队可以完全覆盖， 那么比t更大的时间一定可以 所以就可以先二分时间，那么如何判断每一个时间是否可行 因为军队是可以同时移动的，并且军队在深度小的结点是比在深度大的结点更优的 所以对于每一个军队，计算出在当前时间限制t内往上跳能跳的深度最小的结点， 如果这个军队可以跳到1号结点，就让它暂时闲置在1号结点的子节点，然后可以枚 举1号结点的所有子节点，计算出以这个子节点为根的子树除开它的根是否已经被 覆盖，对于所有闲置的军队，若它剩余的时间不够它到根节点在返回，就让它直接 驻扎在当前结点。 结合代码理解 #include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int N = 5e4 + 5;typedef long long ll;ll dist[N];int dt[N], fa[N][25], tot, sn[N], ...

CF1406E Deleting Numbers 交互题 考虑枚举所有n以内的质数,用一次查询B,再进行查询A,若返回1,则说明a为当前枚举的质数的倍数 考虑到唯一分解定理,再不断枚举当前质数的幂次方,进行查询A,最终可以确定a. 很明显,这样的操作次数是质因子数+幂次方数的,而100000内的质数有9600多个,所以会超出题目的限制 可以按两种情况考虑 1.x≤nx\le\sqrt{n}x≤n​ 直接暴力枚举 2.x>nx>\sqrt{n}x>n​,这时假设已经枚举完了所有的小质数,得到的答案为ans A:ans>1,这时集合内就只剩大于 n\sqrt{n}n​ 的质数了,所以直接对每一个质数*ans进行查询A,若返回1,则为答案 B:ans=1,说明答案为一个质数,但不可能直接枚举每一个质数,所以可以对每一个质数进行分块处理,分成 n\sqrt{n}n​ 块,首先 对每一块中的所有数进行一次查询B,再对1进行一次查询A,比较是否有减少的数,若有,就直接在块中暴力查询即可 代码 #include<iostream>#include<cstdi ...

P3704 [SDOI2017]数字表格 直接开始推式子,令 k=min(n,m)k=min(n,m)k=min(n,m) ans=∏i=1n∏j=1mfgcd(i,j)=∏d=1kfd∑i=1n∑j=1m[gcd(i,j)=d]ans=\prod_{i=1}^n\prod_{j=1}^mf_{gcd(i,j)}=\prod_{d=1}^kf_d^{\sum\limits_{i=1}^n\sum\limits_{j=1}^m[gcd(i,j)=d]} ans=i=1∏n​j=1∏m​fgcd(i,j)​=d=1∏k​fdi=1∑n​j=1∑m​[gcd(i,j)=d]​ 上面那坨非常明显的莫反 =∏d=1kfd∑d∣Tμ(Td)⌊nT⌋⌊mT⌋=∏T=1k∏d=1kfdμ(Td)⌊nT⌋⌊mT⌋=∏T=1k(∏d=1kfdμ(Td))⌊nT⌋⌊mT⌋=\prod_{d=1}^kf_d^{\sum\limits_{d|T}\mu(\frac{T}{d})\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor}=\prod_{T=1}^k\pr ...

队列 queue<int> name;name.front()访问对头name.push(a)入队name.pop()出队name.empty()队列为空返回truename.size()返回队列大小 双端队列 deque<int>name;name.front()访问对头name.back()访问队尾name.push_front(a)对头入队name.push_back(a)队尾出队name.pop_front()对头出队name.pop_back()队尾出队name.empty()队列为空返回truename.size()返回队列大小 优先队列(堆) priority_queue<int>name;默认大根堆priority_queue<int,vector<int>,greater<int>>name小根堆priority_queue<int,vector<int>,less<int>>name大根堆name.top()访问对头name.pop()出队name.empty ...

状压DP CF1313D Happy New Year 化简一下题意 给定 nnn 条线段,让你覆盖 mmm 个点,保证每个点最多被覆盖 kkk 次,求最多有多少个点被奇数条线段覆盖 数据范围 1≤n≤105,1≤m≤109,1≤k≤81\le n\le 10^5,1\le m\le 10^9,1\le k\le 81≤n≤105,1≤m≤109,1≤k≤8 很明显,时间复杂度不能与 mmm 相关,注意到 kkk 很小,所以可以考虑状压DP 将线段的端点离散化后存下来,排序后枚举每个端点 定义 fi,jf_{i,j}fi,j​ 表示枚举到前 iii 个点, jjj 表示当前覆盖的线段,第 jjj 的二进制表示中 1 的数量为覆盖的线段数量 用 viv_ivi​ 表示 iii 中有多少个1,len表示两个相邻端点间的距离,mmm 表示覆盖了当前线段后的 jjj 分情况考虑当前枚举的端点 1.若为左端点 fi,j=max(fi,j,fi−1,j+(vj mod 2)×len)fi,m=max(fi,m,fi−1,j+(vj mod 2)×(len−1))+(vj+1) mod 2)f_{i ...

题面比较长,但其实就是一道板子题 根据题意, ga≡A(mod p),gb≡B(mod p)g^a\equiv A(mod~p),g^b\equiv B(mod~p)ga≡A(mod p),gb≡B(mod p),可以直接通过BSGS求出 a,ba,ba,b 的值,然后直接用快速幂算出来即可 关于BSGS,可以看看我的博客 代码 #include<iostream>#include<cmath>#include<unordered_map>using namespace std;typedef long long ll;int ksm(int a, int b, int p){ int res = 1; while (b) { if (b & 1) res = (ll)res * a % p; a = (ll)a * a % p; b >>= 1; } return res;}int BSGS(in ...