差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:legal_string:jxm2001:contest:cf_feb21 [2021/02/16 10:32]
jxm2001
+++ 2020-2021:teams:legal_string:jxm2001:contest:cf_feb21 [2021/02/16 19:42] (当前版本)
jxm2001 [题解]
@@ 行 133: / 行 133: @@
 		enter(ans);
 	}
+	return 0;
+}
+</code>
+</hidden>
+===== XOR Sums =====
+==== 题意 ====
+给定正整数序列 $A_1,A_2\cdots A_n$，接下来 $Q$ 个询问。
+定义一个集合的权值为该集合所有元素的异或和，每次询问元素个数不超过 $M$ 的所有子集的权值和。
+==== 题解 1 ====
+考虑预处理出元素个数分别为 $1\sim n$ 的子集的权值和，然后 $O(1)$ 处理询问。
+按位处理贡献，假设第 $i$ 位为 $1$ 的数有 $c_1$ 个，则第 $i$ 位为 $0$ 的数有 $c_0=n-c_1$ 个。
+于是对子集元素个数为 $k$ 的答案产生的贡献为
+$$
+^i\sum_{j\in odd}^{1\le j\le c_1}{c_1\choose j}{c_0\choose k-j}
+$$
+令 $f(x)=\sum_{i\in odd}^{1\le i\le c_1}{c_1\choose i}$，$g(x)=\sum_{i=0}^{c_0}{c_0\choose i}$，于是贡献为
+$$
+^i[x^k]f(x)g(x)
+$$
+考虑 $\text{NTT}$ 卷积，总时间复杂度 $O(n\log n\log v)$。
+ps. 比赛时考虑 $f_1(x)=(x+1)^{c_1},f_2(x)=(-x+1)^{c_1},g(x)=(x+1)^{c_0}$，然后贡献为 $2^i[x^k]\cfrac {(f_1(x)-f_2(x))g(x)}2$。
+然后脑抽使用了多项式 $\text{Pow}$ 算 $f_1,f_2,g$，时间复杂度也是 $O(n\log n\log v)$，但直接 $T$ 飞了，其实直接 $O(n)$ 二项式就好了。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=2e5+5,Mod=998244353,inv2=(Mod+1)/2;
+int quick_pow(int a,int k){
+	int ans=1;
+	while(k){
+		if(k&1)ans=1LL*ans*a%Mod;
+		a=1LL*a*a%Mod;
+		k>>=1;
+	}
+	return ans;
+}
+namespace Poly{
+	const int G=3;
+	int rev[MAXN<<2],Pool[MAXN<<3],*Wn[30];
+	void init(){
+		int lg2=0,*pos=Pool,n,w;
+		while((1<<lg2)<MAXN*2)lg2++;
+		n=1<<lg2,w=quick_pow(G,(Mod-1)/(1<<lg2));
+		while(~lg2){
+			Wn[lg2]=pos,pos+=n;
+			Wn[lg2][0]=1;
+			_for(i,1,n)Wn[lg2][i]=1LL*Wn[lg2][i-1]*w%Mod;
+			w=1LL*w*w%Mod;
+			lg2--;n>>=1;
+		}
+	}
+	int build(int k){
+		int n,pos=0;
+		while((1<<pos)<=k)pos++;
+		n=1<<pos;
+		_for(i,0,n)rev[i]=(rev[i>>1]>>1)|((i&1)<<(pos-1));
+		return n;
+	}
+	void NTT(int *f,int n,bool type){
+		_for(i,0,n)if(i<rev[i])
+		swap(f[i],f[rev[i]]);
+		int t1,t2;
+		for(int i=1,lg2=1;i<n;i<<=1,lg2++){
+			for(int j=0;j<n;j+=(i<<1)){
+				_for(k,j,j+i){
+					t1=f[k],t2=1LL*Wn[lg2][k-j]*f[k+i]%Mod;
+					f[k]=(t1+t2)%Mod,f[k+i]=(t1-t2)%Mod;
+				}
+			}
+		}
+		if(!type){
+			reverse(f+1,f+n);
+			int div=quick_pow(n,Mod-2);
+			_for(i,0,n)f[i]=(1LL*f[i]*div%Mod+Mod)%Mod;
+		}
+	}
+	void Mul(int *f,int _n,int *g,int _m,int xmod=0){
+		int n=build(_n+_m-2);
+		_for(i,_n,n)f[i]=0;_for(i,_m,n)g[i]=0;
+		NTT(f,n,true);NTT(g,n,true);
+		_for(i,0,n)f[i]=1LL*f[i]*g[i]%Mod;
+		NTT(f,n,false);
+		if(xmod)_for(i,xmod,n)f[i]=0;
+	}
+}
+const int MAXS=30;
+int c0[MAXS],c1[MAXS],ans[MAXN];
+int frac[MAXN],inv[MAXN],f[MAXN<<2],g[MAXN<<2];
+int C(int n,int m){
+	return 1LL*frac[n]*inv[m]%Mod*inv[n-m]%Mod;
+}
+int main()
+{
+	Poly::init();
+	int n=read_int();
+	_for(i,0,n){
+		int a=read_int();
+		_for(j,0,MAXS){
+			if(a&1)c1[j]++;
+			else c0[j]++;
+			a>>=1;
+		}
+	}
+	frac[0]=1;
+	_rep(i,1,n)frac[i]=1LL*i*frac[i-1]%Mod;
+	inv[n]=quick_pow(frac[n],Mod-2);
+	for(int i=n;i;i--)inv[i-1]=1LL*inv[i]*i%Mod;
+	for(int i=MAXS-1;i>=0;i--){
+		_rep(j,0,c1[i]){
+			if(j%2==0)f[j]=0;
+			else f[j]=C(c1[i],j);
+		}
+		_rep(j,0,c0[i])g[j]=C(c0[i],j);
+		Poly::Mul(f,c1[i]+1,g,c0[i]+1);
+		_rep(j,1,n)ans[j]=(2LL*ans[j]+f[j])%Mod;
+	}
+	_rep(i,1,n)ans[i]=(ans[i]+ans[i-1])%Mod;
+	int q=read_int();
+	while(q--)
+	enter(ans[read_int()]);
+	return 0;
+}
+</code>
+</hidden>
+==== 题解 2 ====
+设 $\text{dp}(i,j,k)$ 表示子集大小为 $i$，仅考虑位数 $j$，且异或和为 $k$ 的子集个数。
+可以 $O(n\log v)$ 得到答案，具体见该[[https://www.codechef.com/viewsolution/42840665|代码]]
+===== Another Tree with Number Theory =====
+==== 题意 ====
+给定一棵以 $1$ 为根的树，接下来 $q$ 次询问。
+每次询问给定一个结点 $u$ 初始权值 $w$。当结点 $u$ 拥有权值 $w$ 时，如果结点 $u$ 是叶子结点，则该权值被吸收。
+否则记 $u$ 的儿子结点数为 $k$。若 $k\mid w$，则结点 $u$ 将权值均分为 $k$ 份并转移到每个儿子结点并继续下传，否则该权值损失。
+问每次损失的权值。
+==== 题解 ====
+首先如果某个结点只有一个儿子，则将该结点与其儿子合并。
+对结点 $u$，设他到某个叶子结点的路径上所有点的儿子结点数的乘积为 $k$。若 $k\mid w$，则该叶子结点能吸收权值 $\frac wk$，否则无法吸收。
+考虑对每个结点用 $\text{map}$ 维护他每个 $k$ 对应的叶子节点数。
+由于每次向上一级 $k$ 至少乘以 $2$，于是一个叶子结点最多对 $O(\log w)$ 个祖先节点有贡献。故维护 $\text{map}$ 的时间复杂度为 $O\left(n\log w\log n\right)$。
+对每个询问，用其存储在权值对应的桶中，然后跑一遍埃氏筛枚举因子计算贡献。
+总时间复杂度 $O(n\log n\log w+w\log w+q\times \text{divisors}(w)\log n)$。
+如果用哈希表替代 $\text{map}$，时间复杂度为 $(n\log w+w\log w+q\times \text{divisors}(w))$。
+ps. $\text{map}$ 访问空建默认返回 $0$ 但非常慢，不建议利用该特性，推荐用 $\text{find}$ 特判后再访问。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=1e5+5,MAXW=1e6+5;
+struct Edge{
+	int to,next;
+}edge[MAXN];
+int head[MAXN],edge_cnt;
+void Insert(int u,int v){
+	edge[++edge_cnt]=Edge{v,head[u]};
+	head[u]=edge_cnt;
+}
+int idx[MAXN],ch[MAXN],ans[MAXN];
+map<int,int> d[MAXN];
+vector<pair<int,int> > query[MAXW];
+void dfs(int u){
+	if(!ch[u]){
+		d[u][1]=1;
+		return;
+	}
+	for(int i=head[u];i;i=edge[i].next){
+		int v=edge[i].to;
+		dfs(v);
+		if(ch[u]==1){
+			idx[u]=idx[v];
+			return;
+		}
+		v=idx[v];
+		for(map<int,int>::iterator it=d[v].begin();it!=d[v].end();++it){
+			LL k=1LL*ch[u]*it->first;
+			if(k<MAXW)
+			d[u][k]+=it->second;
+		}
+	}
+}
+int main()
+{
+	int n=read_int();
+	_rep(i,1,n)idx[i]=i;
+	_rep(i,2,n){
+		int p=read_int();
+		ch[p]++;
+		Insert(p,i);
+	}
+	dfs(1);
+	int q=read_int();
+	_for(i,0,q){
+		int v=read_int(),w=read_int();
+		ans[i]=w;
+		query[w].push_back(make_pair(i,idx[v]));
+	}
+	_for(i,1,MAXW){
+		for(int j=i;j<MAXW;j+=i){
+			_for(k,0,query[j].size()){
+				int u=query[j][k].second;
+				if(d[u].find(i)!=d[u].end())
+				ans[query[j][k].first]-=j/i*d[u][i];
+			}
+		}
+	}
+	_for(i,0,q)
+	enter(ans[i]);
 	return 0;
 }
 </code>
 </hidden>

CVBB ACM Team

用户工具

站点工具

差别

页面工具