搜索结果
查询Tags标签： FWT，共有 8条记录-
2022.6.28
SP26017 GCDMAT - GCD OF MATRIX比较傻逼的题目，显然答案等于 \[\large sum_{d=1}^n \varphi_d \times \lfloor \frac n d \rfloor \times \lfloor \frac m d \rfloor \]容斥+整除分块即可。SP26045 GCDMAT2 - GCD OF MATRIX (hard)和上题相同，不过数据范围变大了，要卡…
2022/6/28 23:32:20 人评论 次浏览 -
FWT 学习笔记
快速沃尔什变换（FWT）学习笔记 What 这是啥呀 \(~~~~\) 快速沃尔什变换也用于解决一些卷积问题，所不同的是它解决的卷积的下标一般由位运算代替加法，因此也可以用集合卷积来表示其所能解决的问题。 \(~~~~\) 才疏学浅，理解不深，仅能至此。 How 怎么做 \(~~~~\) 显然暴…
2022/5/3 23:13:00 人评论 次浏览 -
省选模拟赛（V）
冲刺国赛5月2日第二场 \(t1\) 沉迷前缀和无法自拔，觉得扫描线是离散位置修改不好操作，没想到其实有零的情况只多了一点点 \(t2\) 在想回滚莫队，但是撤回操作不会很好地处理，并没有领会随机的意图…… \(t3\) 来者不善又是 \(FWT\)……A. a 以 \(i\) 为右端点的最远左端…
2022/5/2 23:12:53 人评论 次浏览 -
[Codeforces]662C - Binary Table（FWT）
一些套路的整合题，是一个好题。 题意： 给定一个\(n\times m\)的01矩阵，每次可以选择一行或者一列进行取反，问任意进行操作后，矩阵中剩下的1最少有几个。 \(n\le 20, m\le 10^5\) 先进行一下转化，首先注意到\(n\)是很小的，有一个贪心策略是，确定了行的取反状态后，…
2021/9/6 6:06:54 人评论 次浏览 -
[Codeforces]662C - Binary Table（FWT）
一些套路的整合题，是一个好题。 题意： 给定一个\(n\times m\)的01矩阵，每次可以选择一行或者一列进行取反，问任意进行操作后，矩阵中剩下的1最少有几个。 \(n\le 20, m\le 10^5\) 先进行一下转化，首先注意到\(n\)是很小的，有一个贪心策略是，确定了行的取反状态后，…
2021/9/6 6:06:54 人评论 次浏览 -
FWT整理
FWT by AmanoKumiko 1.Or \[A_i=∑_{j|i=i}Aj \]\[FWT[A]=merge(FWT[A_0],FWT[A_0]+FWT[A_1]) \]\[UFWT[A]=merge(UFWT[A_0],UFWT[A_1]-UFWT[A_0]) \] 2.And \[A_i=∑_{j\ and\ i=i}Aj \]\[FWT[A]=merge(FWT[A_0]+FWT[A_1],FWT[A_1]) \]\[UFWT[A]=merge(UFWT[A_0]-UFWT[A_…
2021/8/23 23:07:33 人评论 次浏览 -
FWT整理
FWT by AmanoKumiko 1.Or \[A_i=∑_{j|i=i}Aj \]\[FWT[A]=merge(FWT[A_0],FWT[A_0]+FWT[A_1]) \]\[UFWT[A]=merge(UFWT[A_0],UFWT[A_1]-UFWT[A_0]) \] 2.And \[A_i=∑_{j\ and\ i=i}Aj \]\[FWT[A]=merge(FWT[A_0]+FWT[A_1],FWT[A_1]) \]\[UFWT[A]=merge(UFWT[A_0]-UFWT[A_…
2021/8/23 23:07:33 人评论 次浏览 -
算法学习————FWT
解决问题 \[C_i = \sum\limits_{j\bigoplus k = i} A_j\times B_k \]其中\(\bigoplus\)为or，and，xor，已知A和B，求解C 和FFT还有NTT的思想都是一样的，考虑在FFT的时候，我们是从系数法转化成点值法 对A和B本身FFT一次，想乘后得到C，然后用逆运算再把点值法转化成系数…
2021/7/2 9:21:32 人评论 次浏览
