#14 CF1103D & CF1119H & CF908H
Professional layer
题目描述
点此看题
解法
又和正解想到一块去了，话说我为什么现在觉得这些题都不是特别难了。
首先求出所有数的 \(\gcd\)，记为 \(G\)，那么 \(G\) 的质因子种类至多 \(m=11\) 种，并且每次操作至少都要把一种质因数的次数归零，所以可以得到操作次数也 \(\leq m\)
那么不难设计一个暴力的状压 \(dp\)，设 \(f[i][s]\) 表示已经操作了 \(i\) 个数，解决的质因数集合是 \(s\)，的最小花费总和，使用子集枚举可以做到 \(O(nm\cdot 3^m)\)
优化显然要在这个 \(n\) 上下功夫，我们考虑一个数的作用是解决某个 \(s\)，那么从 \(s\) 的角度考虑，我们只需要保留花费最小的 \(m\) 个数就可以避免冲突。
那么我们可以得到 \(O(m\cdot 2^m)\) 个形如 \((i,s)\) 的有效转移，表示数 \(i\) 可以解决集合 \(s\)，转移的时候按 \(i\) 分层，上一层向下一层转移（因为一个数最多解决一个集合），时间复杂度 \(O(m^2\cdot3^m)\)
剩下的问题是如何求出这些有效转移，我们先把 \(a_i\) 只保留 \(G\) 中的质因子，这样最多只有 \(12000\) 左右的种类，对于每个种类选取前 \(m\) 个加入到所有可能解决的集合中，最后对于每种 \(s\) 再保留前 \(m\) 个即可。
#include
#include
#include
#include
using namespace std;
#define int long long
const int M = 1000005;
const int N = 1<<11;
const int inf = 1e15;
const int MOD = 1e6+7;
#define pb push_back
int read()
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int n,m,k,G,ans,a[M],b[M],p[12],tot,F[MOD];
int sum[N],f[12][N],g[12][N];vector v[M],vc[N];
vector> d,t;
struct edge{int h,next;}e[M];
int gcd(int a,int b) {return !b?a:gcd(b,a%b);}
int cmp(int i,int j) {return b[i] &v)
{
int sz=min((int)v.size(),m);
sum[0]=1;sort(v.begin(),v.end(),cmp);
for(int i=0;ic) f[i][s]=c,d.pb({i,s});
}
signed main()
{
n=read();k=read();
for(int i=1;i<=n;i++) G=gcd(G,a[i]=read());
for(int i=1;i<=n;i++) b[i]=read();
//decompose G
for(int i=2;i*i<=G;i++) if(G%i==0)
{p[m++]=i;while(G%i==0) G/=i;}
if(G>1) p[m++]=G;
//find all useful trans
for(int i=1;i<=n;i++)
{
int x=a[i],y=1;
for(int j=0;j=inf)?-1:ans);
}
Triple
题目描述
点此看题
解法
我无语了， 几句话就证出来了，那不是显得我说了一堆废话吗？
真的被教育了，花了整整一个下午才完全明白，你需要完全理解异或卷积的原理才能理解本题。
约定：记 \(x\odot y\) 表示 \(x\and y\) 的二进制位上 \(1\) 个数的奇偶性。
发现本题就是黎明前的巧克力的加强版，我们提出一个更为普遍的问题并尝试解决它：集合中有 \(m\) 个元素，给定 \(n\) 个集合幂级数 \(f_i=\sum_{j=0}^{k-1}w_j\cdot x^{a_{i,j}}\)，其中 \(k\) 和 \(w\) 数组都已知，求 \(\prod_{i=1}^n f_i\) 的每一项。
考虑暴力做法就是对每个 \(f_i\) 分别快速沃尔什变换（下文简称变换）然后乘起来得到 \(F\)，现在我们考虑快速求出 \(F\)，我们下文着重讨论 \(F\) 的第 \(p\) 位所具有的性质。
根据异或卷积的基本知识可以知道，\(F_p\) 可以写成 \(\prod_{s=0}^{2^k-1}(\sum_{j=0}^{k-1} \pm w_j)^{c_s}\) 的形式，其中 \(s\) 代表一种系数组合，如果它的第 \(j\) 位为 \(1\) 则 \(w_j\) 前面的符号是 \(-1\)，如果它的第 \(j\) 位为 \(0\) 则 \(w_j\) 前面的符号是 \(1\)，\(c_s\) 就表示这种系数组合在所有 \(\hat f_i\) 中的出现次数。
值得注意的是，\(c_s\) 和 \(w_j\) 完全没有关系，每个 \(p\) 上天然具有这样的 \(c\) 数组，更具体地，可以写出它的表达式：
\[c_s=\sum_{i=1}^n\prod_{j=0}^{k-1}[(-1)^{p\odot a_{i,j}}=(-1)^{popcount(s\and 2^j)}] \]既然 \(w_j\) 是系数，那么我们可以通过调整系数构造方程反解出 \(c_s\)，考虑到 \(T\subseteq\{0,1...k-1\}\) 的数量正好有 \(2^k\) 个，对于每个 \(T\) 我们考虑构造出对应的方程。
设 \(z_{i,T}=\sum_{j\in T} a_{i,j}\)，我们考虑集合幂级数 \(h_T=\sum_{i=1}^n x^{z_{i,T}}\)，对其进行变换得到 \(\hat h_T\)，记 \(g_T=\hat h_{T,p}\)（我们还是只考虑第 \(p\) 位），那么现在考虑构建 \(c_s\) 和 \(g_T\) 之间的等式关系，需要利用 \(\odot\) 对异或运算的分配律：
\[(i\odot j)\oplus (i\odot k)=i\odot(j\oplus k) \]那么可以推导出：
\[g_T=\sum_{i=1}^n (-1)^{p\odot z_{i,T}}=\sum_{i=1}^n\prod_{j\in T}(-1)^{p\odot a_{i,j}} \]\(\prod_{j\in T} (-1)^{p\odot a_{i,j}}\) 可以看成集合幂级数 \(f_i\) 给位置 \(p\) 的贡献，考虑如果 \((-1)^{p\odot z_{i,T}}=-1\)，那么贡献是 \(-1\)；如果 \((-1)^{p\odot z_{i,T}}=1\)，那么贡献是 \(1\)；把这东西对应到 \(c_s\) 上去，这里 \(c_s\) 的意义理解为对 \(n\) 个集合幂级数贡献的求和，那么如果 \((-1)^{T\odot s}=-1\)，则贡献 \(-c_s\)；如果 \((-1)^{T\odot s}=1\)，那么贡献 \(c_s\)（结合上面的表达更好理解，原因就是要 \(T\) 和 \(s\) 中同时出现才贡献 \(-1\)），所以可以推导出：
\[g_T=\sum_{s=0}^{2^k-1}(-1)^{T\odot s} c_s \]发现 \((-1)^{T\odot s}\) 正好是变换的系数，所以我们把 \(g\) 逆变换就可以得到 \(c\)，时间复杂度 \(O(n2^k+(m+k)2^{m+k})\)
算法流程建议参考一下我带注释的代码，可以帮助你再次梳理思路：
#include
#include
using namespace std;
const int M = 1<<17;
const int MOD = 998244353;
const int inv2 = (MOD+1)/2;
#define int long long
int read()
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int n,m,k,W[M],w[M],lg[M],f[M],g[M],z[M][5],sum[M];
int qkpow(int a,int b)//快速幂
{
int r=1;
while(b>0)
{
if(b&1) r=r*a%MOD;
a=a*a%MOD;
b>>=1;
}
return r;
}
void fwt(int *a,int n,int op)//异或卷积
{
for(int i=1;i>1]+1;
for(int j=0;j>j&1) W[i]=(W[i]-w[j]+MOD)%MOD;
else W[i]=(W[i]+w[j])%MOD;
}
}
for(int i=1;i<=n;i++)//读入集合幂级数
{
for(int j=0;j New Year and Boolean Bridges
题目描述
点此看题
分享一段最近看到的话：
感觉反演一般是增添一个求和号之后再交换求和顺序，以退为进简化问题？
解法
感觉本题更偏向于构造，现在看也并没有什么难点。
关系为 A 的 \((i,j)\) 一定处在同一个强连通块中，所以可以把它们先连起来。然后如果关系为 X 的 \((i,j)\) 缩在了一个强连通块中那么一定无解，可以把这个先判断掉。
假设我们已经确定了有向图的强连通块，那么剩下的点一定是连成一条链，这样就可以轻易地满足所有限制。而强联通块内部为了节省边数一定是连城大环，设点数 \(\geq 2\) 的强连通块有 \(i\) 个，那么答案就是 \(n+i-1\)
我们需要尽可能减少 \(i\)，就需要把某些强连通分量合并到一起。考虑这样的强连通分量最多 \(23\) 个，可以用 \(dp\) 解决问题，设 \(dp(i,s)\) 表示共有 \(i\) 个合并后的强连通分量，其包含原来强连通分量的集合是 \(s\)，可以预处理出 \(dp(0,s)\)，转移：
\[dp(i,s)=\sum_{a|b=s} dp(i-1,a)\cdot dp(i-1,b) \]注意转移并不需要要求集合 \(a,b\) 不交，因为如果一个集合合法，那么其子集也一定合法。显然可以用 \(\tt fwt\) 优化转移，而且每次转移之后不需要逆变换回去，我们只需要判断 \(dp(i,U)\) 是否合法即可，那么对单项进行逆变换只需要子集反演即可，时间复杂度 \(O(\frac{n}{2}\cdot 2^{n/2})\)
为了防止 \(dp\) 数组在过程中乘爆需要带上模数，出错概率极低。
#include
const int M = 55;
const int N = 1<<23;
const int MOD = 1e9+7;
int read()
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int n,m,fa[M],b[M],ban[M],siz[M];char s[M][M];
int f[N],g[N],lg[N];
int find(int x)
{
if(x!=fa[x]) fa[x]=find(fa[x]);
return fa[x];
}
void fwt(int *a,int n)
{
for(int i=1;i1) b[i]=++m;
if(!m) {printf("%d\n",n-1);return 0;}
for(int i=1;i<=n;i++) for(int j=1;j>1]+1;
int low=i&(-i),x=lg[low]+1;
if(!((i^low)&ban[x])) f[i]=f[i^low];
}
if(f[(1<