题目链接 题意 : 给你一个a数组和b数组,构造出A[i][j]矩阵(A[i][j] = a[i xor j]) 给出等式 A * x = b ( mod p ) n等于4的时候有: A[0][0]*x[0] + A[0][1]*x[1] + A[0][2]*x[2] + A[0][3]*x[3] = b[0] (mod p)A[1][0]*x[0] + A[1][1]*x[1] + A[1][2]*x[2] + A[1][3]*x[3] = b[1] (mod p)A[2][0]*x[0] +

福哥答案2020-06-22: 1.遍历法时间复杂度:O(N)最好空间复杂度:O(1)平均空间复杂度:O(sqrt(N))最坏空间复杂度:O(N)[0,N/2]依次遍历,符合条件的就是需要的结果. 2.位运算法最好时间复杂度:O(1)平均时间复杂度:O(sqrt(N))最坏时间复杂度:O(N)最好空间复杂度:O(1)平均空间复杂度:O(sqrt(N))最坏空间复杂度:O(N) 1100100 两数和N=100,已知0010100 异或值M=20,已知1010000 差N-M=80,如果差为负数或

hdu 5909 Tree Cutting 题意:一颗无根树,每个点有权值,连通子树的权值为异或和,求异或和为[0,m)的方案数 \(f[i][j]\)表示子树i中经过i的连通子树异或和为j的方案数 转移类似背包,可以用fwt加速 #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long lon

https://www.lydsy.com/JudgeOnline/problem.php?id=4589 n*m*m 做法 dp[i][j] 前i堆石子,异或和为j的方案数 第一重循环可以矩阵快速幂优化 后面求出序列的生成函数可以FWT优化 做log次FWT也很慢(logn*m*logm) 两个合并就是倍增FWT,即先对生成函数的序列做一次正变换,对正变换得到的每个结果快速幂,最后逆变换回去 时间复杂度O(logn*m+m*logm) 生成函数:是质数则系数为1,否则为0 #include<c

题目链接 FWT 题意即,从所有小于\(m\)的质数中,选出\(n\)个数,使它们异或和为\(0\)的方案数. 令\(G(x)=[x是质数]\),其实就是对\(G(x)\)做\(n\)次异或卷积后得到多项式的第\(0\)项. 如果\(n\)很小,可以一次次的FWT.事实上在第一次FWT之后,直接快速幂就行了,不需要中间IFWT转回去. //1652kb 4352ms #include <cstdio> #include <cctype> #include <cstring&g

题目大意:给你$n$个不大于$m$的质数,求有多少种方案,使得这$n$个数的异或和为$0$.其中,$n≤10^9,m≤10^5$. 考虑正常地dp,我们用$f[i][j]$表示前$i$个数的异或和为$j$的方案数. 我们构造一个数组$g$,若i为不大于$m$的质数,则$g[i]=1$,否则为$0$. 那么显然,$f[i][j]=\sum f[i-1][k]\times g[j \oplus k]$.  其中$j \oplus k$表示$j$和$k$的按位异或. 然后我们不难发现,$f[i]为f[

题目链接 hdu5909 题解 设\(f[i][j]\)表示以\(i\)为根的子树,\(i\)一定取,剩余节点必须联通,异或和为\(j\)的方案数 初始化\(f[i][val[i]] = 1\) 枚举儿子\(v\)转移 \[f[i][j] = f[i][j] + \sum\limits_{x \; xor \; y = j} f[i][x] \centerdot f[v][y]\] 发现是一个异或卷积的形式 前面相当于和\(1\)的卷积,后面是和\(f[v]\)的卷积 \(FWT\)即可优化到\

题目描述 给出 $n$ 个数,从中选出两个互不相交的集合,使得第一个集合与第二个集合内的数的异或和相等.求总方案数. 输入 第一行一个正整数 $n$ ,表示巧克力的个数.第二行 $n$ 个整数 $a_i$ 表示每个巧克力的美味值. 输出 输出一行一个整数,表示能使得他们心情契合的吃巧克力的方案数对 998244353 取模的结果. 样例输入 61 2 3 4 5 6 样例输出 80 题解 FWT 首先如果两个集合的异或相等,那么它们的异或为0.原问题转化为求选出一个异或和为0的集合并分为两个即可

题目:https://www.lydsy.com/JudgeOnline/problem.php?id=4589 一开始异或和为0的话先手必败.有 n 堆,每堆可以填那些数,求最后异或和为0的方案数,就是一个快速幂的异或FWT. 注意快速幂的过程中对那些数组直接乘就行,不用总是FWT!!! 为什么比Zinn慢了1008ms? #include<iostream> #include<cstdio> #include<cstring> #include<algorit

题目链接  Hard Nim 设$f[i][j]$表示前$i$个数结束后异或和为$j$的方案数 那么$f[i][j] = f[i-1][j$ $\hat{}$ $k]$,满足$k$为不大于$m$的质数. 这个$DP$太暴力了.让我们冷静分析. 设不大于m的质数从小到大分别为$c_{1}$, $c_{2}$, ..., $c_{k}$ $f[i][j] = ∑f[i-1][j$ $\hat{}$ $c[k]]$, 我们令$g[c[i]]$为$1$,其余为$0$. $f[i][j] = ∑f[i-1

题目描述 Claris和NanoApe在玩石子游戏,他们有n堆石子,规则如下: 1. Claris和NanoApe两个人轮流拿石子,Claris先拿. 2. 每次只能从一堆中取若干个,可将一堆全取走,但不可不取,拿到最后1颗石子的人获胜. 不同的初始局面,决定了最终的获胜者,有些局面下先拿的Claris会赢,其余的局面Claris会负. Claris很好奇,如果这n堆石子满足每堆石子的初始数量是不超过m的质数,而且他们都会按照最优策略玩游戏,那么NanoApe能获胜的局面有多少种. 由于答案可能

题目传送门 题目大意:给你一个序列,定义一个子序列的权值表示子序列中元素的异或和,现在让你选出两个互不相交的子序列,求选出的这两个子序列权值相等的方案数,$n,a_{i}\leq 10^{6}$ 这是一道考察对$FWT$算法理解的好题.然而我并不会 思路来自出题人的题解 假设权值最大值为$m$ 暴力怎么搞?背包$DP$一下 定义$f(i,j)$表示现在遍历到了第$i$个元素,选出的两个子序列异或和为$j$的方案数,容易得到方程: $f(i,j)=f(i-1,j)+2*f(i-1,j\;xor\;

最近舟游疯狂出货,心情很好~ FFT FWT 快速傅里叶变换(FFT) 具体的推导见这篇:胡小兔 - 小学生都能看懂的FFT!!! (写的很好,不过本小学生第一次没看懂0.0) 总结下关键内容 ~ Part 0 ~ 点值表示 对于一$n$项多项式$A(x)=a_0+a_1x+a_2x^2+...+a_{n-1}x^{n-1}$ 我们代入$n$个不同的数$x_i$,得到$n$个值$y_i=A(x_i)$ 则称这$n$个有序数对$(x_i,y_i)$为多项式$A(x)$的点值表示(可以认为是$xOy

目录 与卷积: 代码: 或卷积: 代码: 异或卷积: 代码: FST:子集卷积 代码: 例题: CF914G 代码: uoj310[UNR #2]黎明前的巧克力 代码: CF662C Binary Table 代码: FWT可以解决位运算卷积问题. 即\(h(i)=\sum\limits_{j⊕k=i} f(j)*g(k)\),其中"⊕"表示位运算. 与卷积: 定义\(f\)到\(F\)的变换:\(F(i)=\sum\limits_{j\&i==i}^{ }f(j)\). 这样

题面:https://www.lydsy.com/JudgeOnline/problem.php?id=4589 题意 求选恰好n个数,满足每个数都是不大于m的质数,且它们的异或和为0的方案数. 解法 设f(i,j)为选了i个数,异或和为j的方案数,转移如下: \[ f(i,j)=\sum_{k\bigoplus{p}=j}{f(i-1,k)*[p\quad is\quad prime]} \] 我们发现这是一个异或卷积的形式,状态向量一开始只有0的地方是1,它与一个只有质数下标处值为1的向量卷

正题 题目链接:https://www.luogu.com.cn/problem/CF1119H 题目大意 \(n\)个可重集,第\(i\)个里有\(x\)个\(a_i\),\(y\)个\(b_i\),\(z\)个\(c_i\). 对于每个\(t\in[0,2^k)\)求每个集合里取出一个数使它们异或起来等于\(t\)的方案数. 解题思路 如果直接\(n\)个东西\(FWT\)起来肯定过不了,我们需要根据每个集合里只有三种数这个性质来优化. 因为是\(xor\)卷积,所以第\(i\)个位置\(F

Codeforces 题目传送门 & 洛谷题目传送门 FWT 的 immortal tea %%% 首先我们可以写出一个朴素的 \(dp\),设 \(dp_{i,j}\) 表示考虑前 \(i\) 个三元组中取数异或和为 \(j\) 的方案数,那么显然有 \(dp_{i,j}=Xdp_{i-1,j\oplus a_i}+Ydp_{i-1,j\oplus b_i}+Zdp_{i-1,j\oplus c_i}\),这样暴力复杂度是 \(n2^k\) 的,无法通过. 考虑优化,不难发现这个 \(dp\)

uoj310[UNR #2]黎明前的巧克力(FWT) uoj 题解时间 对非零项极少的FWT的优化. 首先有个十分好想的DP: $ f[i][j] $ 表示考虑了前 $ i $ 个且异或和为 $ j $ 的方案数, 有 $ f[i][j]= f[i-1][j] + 2 * f[i-1][j \oplus a[i]] $ . 可以考虑FWT,但很明显时间复杂度没有优化. 但另一方面,每层的卷积卷的都是 $ 1,0,0,...,2,0,0,... $ 的形式, 这样一来卷之后每项都是 $ -1 $

题意: 给出n个数ai 和m个操作 操作有两种 C x y:将ax的值改为y Q x:求几种方案使得 b1^b2^...^bn=x(ai>=bi) 题解: 先推荐一个不错的题解 题目差不多 我之前就是看着题解做的 http://hi.baidu.com/billdu/item/c749952ab2ab50c2ef10f137 首先我们先不考虑修改 即给你n个数ai 求几种方案使得异或和为x 为了方便起见 我们将原题的条件修改为0≤bi<ai 也就是原来的a数列中每一项都加1 由于我们要求异或和

[BZOJ4671]异或图(斯特林反演) 题面 BZOJ Description 定义两个结点数相同的图 G1 与图 G2 的异或为一个新的图 G, 其中如果 (u, v) 在 G1 与 G2 中的出现次数之和为 1, 那么边 (u, v) 在 G 中, 否则这条边不在 G 中. 现在给定 s 个结点数相同的图 G1...s, 设 S = {G1, G2, . . . , Gs}, 请问 S 有多少个子集的异 或为一个连通图? Input 第一行为一个整数s, 表图的个数. 接下来每一个二进制串

http://acm.hdu.edu.cn/showproblem.php?pid=4901 给定一个序列,要求选出两个集合,S和T,要求S中选中的元素的下标都要小于T中元素的下标.并且说S中元素的异或和要等于T中元素取且的和. 利用dp分左右两边处理 令f[i][j]表示从左到i位置且一定选取a[i]的情况下异或值为j的方案数,g[i][j]同理' 注意最后计数时需要防止重复计数,所以对每个数组下标i,ans += f[i-1][j] * g[i+1][j^a[i]]; #include <c