[CF930E]/[CF944G]Coins Exhibition

25-02-06 34

关于[CF930E]/[CF944G]CoinsExhibition的问题就给大家分享到这里，感谢你花时间阅读本站内容，更多关于CF1039ESummerOenotheraExhibition根号分治

关于[CF930E]/[CF944G]Coins Exhibition的问题就给大家分享到这里，感谢你花时间阅读本站内容，更多关于CF1039E Summer Oenothera Exhibition 根号分治，LCT，ST表、CF632E Thief in a Shop 和 CF958F3 Lightsabers (hard)、CF911F Tree Destruction、CF914G Sum the Fibonacci FWT、子集卷积等相关知识的信息别忘了在本站进行查找喔。

本文目录一览：

[CF930E]/[CF944G]Coins Exhibition
CF1039E Summer Oenothera Exhibition 根号分治，LCT，ST表
CF632E Thief in a Shop 和 CF958F3 Lightsabers (hard)
CF911F Tree Destruction
CF914G Sum the Fibonacci FWT、子集卷积

[CF930E]/[CF944G]Coins Exhibition

题目地址：

CF930E/CF944G

博客地址：

[CF930E]/[CF944G]Coins Exhibition - skylee

题目大意：

一个长度为$k(k\le10^9)$的$01$串，给出$n+m(n,m\le10^5)$个约束条件，其中$n$条描述区间$[l_i,r_i]$至少有一个$0$，其中$m$条描述区间$[l_i,r_i]$至少有一个$1$。求合法的$01$串数量。

思路：

显然直接考虑所有的$k$位，就算$\mathcal O(k)$的线性算法也会超时，因此对于所有的$l_i-1,r_i$以及$0,k$离散化以后考虑这些关键点即可。

设关键点有$lim$个，对所有关键点排序，$tmp[i]$为$i$离散化前对应的数。对所有关键点排序，考虑动态规划，设$f[i][j\in\{0,1,2\}]$表示从后往前考虑第$i\sim lim$个关键点。若$j\in\{0,1\}$，则$f[i][j]$表示$tmp[i]\sim tmp[i+1]$中含有$j$的方案数后缀和。若$j=2$，则$f[i][j]$表示最后一段同时有$0$和$1$的方案数。用$min[j\in\{0,1\}][i]$表示对应约束条件类型为$j$，$i$右侧最近的、对应左端点不在$i$左侧的右端点。状态转移方程如下：

$f[i][0]=f[i+1][0]+f[i+1][1]-f[min[1][i]][1]+f[i+1][2]\times(2^{tmp[i+1]-tmp[i]}-2)$
$f[i][1]=f[i+1][1]+f[i+1][0]-f[min[0][i]][0]+f[i+1][2]\times(2^{tmp[i+1]-tmp[i]}-2)$
$f[i][2]=f[i+1][0]-f[min[0][i]][0]+f[i+1][1]-f[min[1][i]][1]+f[i+1][2]\times(2^{tmp[i+1]-tmp[i]}-2)$

最终答案为$f[0][2]$。

时间复杂度$\mathcal O((n+m)(\log(n+m)+\log k))$。其中$\mathcal O(\log(n+m))$为离散化复杂度，$\mathcal O(\log k)$为快速幂复杂度。

源代码：

#include<cstdio>
#include<cctype>
#include<algorithm>
using int64=long long;
inline int getint() {
    register char ch;
    while(!isdigit(ch=getchar()));
    register int x=ch^''0'';
    while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^''0'');
    return x;
}
constexpr int N=1e5,mod=1e9+7;
std::pair<int,int> p[2][N];
int tmp[N*4+2],min[2][N*4+2],f[N*4+2][3];
inline int power(int a,int k) {
    int ret=1;
    for(;k;k>>=1) {
        if(k&1) ret=(int64)ret*a%mod;
        a=(int64)a*a%mod;
    }
    return ret;
}
int main() {
    const int k=getint(),n=getint(),m=getint();
    int lim=0;
    for(register int i=0;i<n;i++) {
        tmp[++lim]=p[0][i].first=getint()-1;
        tmp[++lim]=p[0][i].second=getint();
    }
    for(register int i=0;i<m;i++) {
        tmp[++lim]=p[1][i].first=getint()-1;
        tmp[++lim]=p[1][i].second=getint();
    }
    tmp[++lim]=k;
    std::sort(&tmp[0],&tmp[lim]+1);
    lim=std::unique(&tmp[0],&tmp[lim]+1)-&tmp[1];
    for(register int i=0;i<=lim;i++) {
        min[0][i]=min[1][i]=lim+1;
    }
    for(register int i=0;i<n;i++) {
        p[0][i].first=std::lower_bound(&tmp[0],&tmp[lim]+1,p[0][i].first)-tmp;
        p[0][i].second=std::lower_bound(&tmp[0],p[0][i].second)-tmp;
        min[0][p[0][i].first]=std::min(min[0][p[0][i].first],p[0][i].second);
    }
    for(register int i=0;i<m;i++) {
        p[1][i].first=std::lower_bound(&tmp[0],p[1][i].first)-tmp;
        p[1][i].second=std::lower_bound(&tmp[0],p[1][i].second)-tmp;
        min[1][p[1][i].first]=std::min(min[1][p[1][i].first],p[1][i].second);
    }
    for(register int i=lim;i;i--) {
        min[0][i-1]=std::min(min[0][i-1],min[0][i]);
        min[1][i-1]=std::min(min[1][i-1],min[1][i]);
    }
    f[lim][0]=f[lim][1]=f[lim][2]=1;
    for(register int i=lim-1;i>=0;i--) {
        int g[3];
        g[0]=(f[i+1][0]-f[min[0][i]][0]+mod)%mod;
        g[1]=(f[i+1][1]-f[min[1][i]][1]+mod)%mod;
        g[2]=(int64)f[i+1][2]*((power(2,tmp[i+1]-tmp[i])-2+mod)%mod)%mod;
        f[i][0]=((int64)f[i+1][0]+g[1]+g[2])%mod;
        f[i][1]=((int64)f[i+1][1]+g[0]+g[2])%mod;
        f[i][2]=((int64)g[0]+g[1]+g[2])%mod;
    }
    printf("%d\n",f[0][2]);
    return 0;
}

CF1039E Summer Oenothera Exhibition 根号分治，LCT，ST表

CF1039E Summer Oenothera Exhibition

LG传送门

根号分治好题。

可以先看我的根号分治总结。

题意就是给出长度为$n$的区间和$q$组询问以及一个$w$，每次询问一个$k$，问最少把一段给定区间划分几次可以满足每一段划分出的子区间的极差不超过$w-k$（以下默认$k$就是$w-k$）。

这题主要有两种写法，一种是$O(n \sqrt nlog n)$的，一种是$O(n^{ \frac 5 3}+n^{ \frac 4 3} log n)$的（本文中默认了$n$和$q$同阶）。

反正先考虑$n^2$暴力，预处理一个ST表，对于每次询问$O(n)$地贪心扫一遍，能划在一个子区间内就划在一个子区间内，这样贪心一定是正确的。

先讲第一种，比较好想，想到从每个点向从它开始能划到它同一个子区间内的最远的点的右边一个点（定义这个点为$h[j]$）一条边，这时我们就想起了弹飞绵羊，可以用LCT维护答案，但是由于每次改变$k$值会可能更改所有点连边情况，的直接这样做是$O(n^2 log n)$的，连暴力都不如。考虑根号分块，先把询问离线，按$k$从小到大排个序，这样划分出区间的长度是单调不减的，如果所连的边的长度不超过$\sqrt n$，就直接用LCT暴力维护，由于边的长度不超过$\sqrt n$，对于所有点最多删边加边$\sqrt n$次，由于每次的复杂度都是$log n$的，所以总的复杂度是$O(n \sqrt n log n)$；如果所要连的边长度超过$\sqrt n$了，就不连这条边；这样我们就用LCT维护了一个森林，对于森林里每棵树的贡献都可以$O(1)$查询，每次询问时先计算一棵树的贡献，到了树根之后就二分它的$h[j]$，跳过去把答案++，再计算$h[j]$所在树的贡献。

#include<cstdio>
#include<cctype>
#include<algorithm>
#include<vector>
#include<cmath>
#define R register
#define I inline
using namespace std;
const int S=100003,M=17,inf=0x7fffffff;
char buf[1000000],*p1,*p2;
I char gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,S,stdin),p1==p2)?EOF:*p1++;}
I int rd(){
	R int f=0; R char c=gc();
	while(c<48||c>57) c=gc();
	while(c>47&&c<58) f=f*10+(c^48),c=gc();
	return f;
}
struct query{int k,p,o;}q[S];
struct splay{int p,d[2],s;}e[S];
int a[S],b[S],l[S],f[S][M],g[S][M],h[S],m;
vector<int> v[S];
I int operator<(query x,query y){return x.k<y.k;}
I int min(int x,int y){return x<y?x:y;}
I int max(int x,int y){return x>y?x:y;}
I int qmn(int x,int y){
	R int i=l[y-x+1];
	return min(f[x][i],f[y-(1<<i)+1][i]);
}
I int qmx(int x,int y){
	R int i=l[y-x+1];
	return max(g[x][i],g[y-(1<<i)+1][i]);
}
I int nrt(int x){return e[e[x].p].d[0]==x||e[e[x].p].d[1]==x;}
I void psu(int x){e[x].s=e[e[x].d[0]].s+e[e[x].d[1]].s+1;}
I void rtt(int x){
	R int f=e[x].p,g=e[f].p,b=e[f].d[1]==x,c=e[x].d[!b];
	if(nrt(f)) e[g].d[e[g].d[1]==f]=x;
	if(c) e[c].p=f;
	e[f].p=x,e[x].p=g,e[x].d[!b]=f,e[f].d[b]=c,psu(f);
}
I void spl(int x){
	for(R int f,g;nrt(x);rtt(x)){
		f=e[x].p,g=e[f].p;
		if(nrt(f))
			rtt((e[g].d[1]==f)^(e[f].d[1]==x)?x:f);
	}
	psu(x);
}
I void acc(int x){
	for(R int y=0;x;x=e[y=x].p)
		spl(x),e[x].d[1]=y,psu(x);
}
I int frt(int x){
	while(e[x].d[0])
		x=e[x].d[0];
	return x;
}
I void cut(int x){acc(x),spl(x),e[e[x].d[0]].p=0,e[x].d[0]=0,psu(x);}
I int fnd(int x,int k){
	R int l=x+1,r=m,m;
	for(m=l+r>>1;l<r;m=l+r>>1)
		qmx(x,m)-qmn(x,m)>k?r=m:l=m+1;
	return m;
}
int main()
	R int n=rd(),W=rd(),Q=rd(),p=sqrt(n),i,j,k,t,s,o;
	for(m=n+1,i=1;i<=n;++i)
		a[i]=f[i][0]=g[i][0]=rd();
	a[m]=f[m][0]=g[m][0]=inf,l[1]=0;
	for(i=2;i<=m;++i)
		l[i]=l[i>>1]+1;
	for(i=1,k=2;k<=m;++i,k<<=1)
		for(j=1;j+k-1<=m;++j)
			f[j][i]=min(f[j][i-1],f[j+(k>>1)][i-1]),g[j][i]=max(g[j][i-1],g[j+(k>>1)][i-1]);
	for(i=1;i<=Q;++i)
		q[i].p=i,q[i].k=W-rd();
	sort(q+1,q+Q+1);
	for(i=1;i<=n;++i)
		h[i]=i,e[i].p=i+1,v[1].push_back(i);
	for(i=1;i<=Q;++i){
		for(o=0,t=0,s=v[i].size();t<s;++t){
			j=v[i][t],cut(j);
			for(k=h[j]+1;qmx(j,k)-qmn(j,k)<=q[i].k&&k-j<=p&&k<=n;++k);
			if(k-j>p)
				b[j]=1;
			else
				h[j]=k,e[j].p=h[j],v[lower_bound(q+1,q+1+Q,(query){qmx(j,h[j])-qmn(j,h[j]),0})-q].push_back(j);
		}
		for(j=1;;j=fnd(j,q[i].k),++o){
			if(!b[j])
				acc(j),spl(j),o+=e[j].s-1,j=frt(j);
			if(j>n)
				break;
		}
		q[q[i].p].o=o-1;
	}
	for(i=1;i<=Q;++i)
		printf("%d\n",q[i].o);
	return 0;
}

注意在实现时有一个重要的细节，删边加边的时候必须二分找它下一个可能改变它$h[j]$值的询问，而不能对于每次询问都把序列扫一遍，这样复杂度会被卡成$n^2$。例如下面的操作就是错误的。

    for(i=1;i<=Q;++i){
        o=0;
        for(j=1;j<=n;++j)
            if(!b[j]){
                for(k=h[j];qmx(j,k)-qmn(j,k)<=q[i].k&&k-j<=p&&k<=n;++k);
                if(k-j>p)
                    b[j]=1,cut(j);
                else
                    if(k^h[j])
                        cut(j),h[j]=k,e[j].p=h[j];
            }
        for(j=1;;j=fnd(j,q[i].k),++o){
            if(!b[j])
                acc(j),spl(j),o+=e[j].s-1,j=frt(j);
            if(j>n) break;
        }
        q[q[i].p].o=o-1;
    }

下面介绍第二种做法。

wxh太神了我看不懂。

然后Itst把wxh的做法写出来了，我就直接丢链接了。

CF632E Thief in a Shop 和 CF958F3 Lightsabers (hard)

Thief in a Shop

n 个物品每个价值 ai，要求选 k 个，可以重复。问能取到哪几个价值？

1 ≤ n, k ≤ 1000，1 ≤ ai ≤ 1000

题解

将选一个物品能取到的价值的 01 生成函数 k 次方即可得到选 k 个物品得到的某个权值的方案数。

出题人卡 NTT 模数，998244353 和 1004535809 都会被卡。然而 469762049 没被卡……

CO int N=1048576;
int a[N];
int rev[N],omg[N];

void NTT(int a[],int lim){
	for(int i=0;i<lim;++i)
		if(i<rev[i]) swap(a[i],a[rev[i]]);
	for(int i=1;i<lim;i<<=1)
		for(int j=0;j<lim;j+=i<<1)
			for(int k=0;k<i;++k){
				int t=mul(omg[lim/(i<<1)*k],a[j+i+k]);
				a[j+i+k]=add(a[j+k],mod-t),a[j+k]=add(a[j+k],t);
			}
}

int main(){
	int n=read<int>(),m=read<int>();
	while(n--) a[read<int>()]=1;
	int len=ceil(log2(m*1000+1)),lim=1<<len;
	for(int i=0;i<lim;++i) rev[i]=rev[i>>1]>>1|(i&1)<<(len-1);
	omg[0]=1,omg[1]=fpow(3,(mod-1)/lim);
	for(int i=2;i<lim;++i) omg[i]=mul(omg[i-1],omg[1]);
	NTT(a,lim);
	for(int i=0;i<lim;++i) a[i]=fpow(a[i],m);
	omg[0]=1,omg[1]=fpow(omg[1],mod-2);
	for(int i=2;i<lim;++i) omg[i]=mul(omg[i-1],omg[1]);
	NTT(a,lim);
	int ilim=fpow(lim,mod-2);
	for(int i=0;i<lim;++i) a[i]=mul(a[i],ilim);
	for(int i=0;i<lim;++i)
		if(a[i]) printf("%d ",i);
	return 0;
}

这题还有背包 DP 做法。将权值排序，对于 i>1，把 ai-=a1。然后做一个最短路径 DP，只要路径长度≤k 就可以凑出来。

之所以要减去 a1，是因为最短路径长度 < k 的结果相当于用了 (k - 长度) 个 a1。

int n,k,a[1005],dp[1000005];
int main(){
	n=read(),k=read();
	for(int i=0;i<n;i++)
		a[i]=read();
	sort(a,a+n);
	for(int i=1;i<n;i++)
		a[i]-=a[0];
	for(int i=1;i<=k*a[n-1];i++)
		dp[i]=3000;
	for(int i=1;i<n;i++)
		for(int j=a[i];j<=a[i]*k;j++)
			dp[j]=min(dp[j],dp[j-a[i]]+1);
	for(int i=0;i<=k*a[n-1];i++)
		if(dp[i]<=k)printf("%d ",k*a[0]+i);
	return 0;
}

Lightsabers (hard)

有 $n$ 个有颜色的球，颜色编号为 $1\dots m$ 中的一个。现在让你从中拿 $k$ 个球，问拿到的球的颜色所构成的可重集合有多少种不同的可能。

注意同种颜色球是等价的，但是两个颜色为 $x$ 的球不等价于一个。

$1\leq n\leq 2\times 10^5,\quad 1\leq m,k\leq n。$

题解

此题把每种颜色能选的数量的 01 生成函数乘起来就好了。

但是有个问题，那就是如果对每个多项式都做长度为 $k$ 的 FFT 的话，是会 TLE 的。

所以需要用到启发式合并，每次选两个长度最小的多项式进行合并。可以用堆来维护，时间复杂度 $O (n \log^2 n)$。

可以使用 STL 的 make_heap，push_heap，pop_heap 系列函数，比 priority_queue 更快。

co double pi=acos(-1);
struct node {
double x,y;
node(){}
node(double x,double y):x(x),y(y){}
};
il node operator+(co node&a,co node&b){
	return (node){a.x+b.x,a.y+b.y};
}
il node operator-(co node&a,co node&b){
	return (node){a.x-b.x,a.y-b.y};
}
il node operator*(co node&a,co node&b){
	return (node){a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x};
}

co int N=1<<18,mod=1009;
int n,m,k,num[N];

node w[N],A[N],B[N];
int rev[N];

void trans(node a[],int lim){
	for(int i=0;i<lim;++i)
		if(i<rev[i]) swap(a[i],a[rev[i]]);
	for(int step=1;step<lim;step<<=1){
		int quot=lim/(step<<1);
		for(int i=0;i<lim;i+=step<<1){
			int j=i+step;
			for(int k=0;k<step;++k){
				node t=w[quot*k]*a[j+k];
				a[j+k]=a[i+k]-t,a[i+k]=a[i+k]+t;
			}
		}
	}
}
void mul_to(co vector<int>&a,co vector<int>&b,vector<int>&c){
	for(int i=0;i<a.size();++i) A[i]=(node){a[i],0};
	for(int i=0;i<b.size();++i) B[i]=(node){b[i],0};
	int len=ceil(log2(a.size()+b.size()-1)),lim=1<<len;
	for(int i=0;i<lim;++i){
		rev[i]=rev[i>>1]>>1|(i&1)<<(len-1);
		w[i]=(node){cos(i*2*pi/lim),sin(i*2*pi/lim)};
	}
	for(int i=a.size();i<lim;++i) A[i]=(node){0,0};
	for(int i=b.size();i<lim;++i) B[i]=(node){0,0};
	trans(A,lim),trans(B,lim);
	for(int i=0;i<lim;++i){
		A[i]=A[i]*B[i];
		w[i].y=-w[i].y;
	}
	trans(A,lim);
	c.resize(a.size()+b.size()-1);
	for(int i=0;i<c.size();++i)
		c[i]=(long long)round(A[i].x/lim)%mod;
}

vector<int> col[N<<1];
int tot;

il bool cmp(int a,int b){
	return col[a].size()>col[b].size();
}
int heap[N],siz;

int main(){
	read(n),read(m),read(k);
	for(int i=1;i<=n;++i) ++num[read<int>()];
	for(int i=1;i<=m;++i){
		if(!num[i]) continue;
		++tot,col[tot].resize(num[i]+1);
		for(int j=0;j<=num[i];++j) col[tot][j]=1;
		heap[++siz]=tot;
	}
	make_heap(heap+1,heap+siz+1,cmp);
	while(siz>=2){
		int x=heap[1];
		pop_heap(heap+1,heap+siz+1,cmp),--siz;
		int y=heap[1];
		pop_heap(heap+1,heap+siz+1,cmp),--siz;
		mul_to(col[x],col[y],col[++tot]);
		heap[++siz]=tot,push_heap(heap+1,heap+siz+1,cmp);
	}
	printf("%d\n",col[tot][k]);
	return 0;
}

CF911F Tree Destruction

题意翻译

给你一棵树,每次挑选这棵树的两个叶子,加上他们之间的边数(距离),然后将其中一个点去掉,问你边数(距离)之和最大可以是多少.

题目描述

You are given an unweighted tree with n n n vertices. Then n−1 n-1 n−1 following operations are applied to the tree. A single operation consists of the following steps:

choose two leaves;
add the length of the simple path between them to the answer;
remove one of the chosen leaves from the tree.

Initial answer (before applying operations) is 0 0 0 . Obviously after n−1 n-1 n−1 such operations the tree will consist of a single vertex.

Calculate the maximal possible answer you can achieve, and construct a sequence of operations that allows you to achieve this answer!

输入输出格式

输入格式：

The first line contains one integer number n n n ( 2<=n<=2⋅105 2<=n<=2·10^{5} 2<=n<=2⋅105 ) — the number of vertices in the tree.

Next n−1 n-1 n−1 lines describe the edges of the tree in form ai,bi a_{i},b_{i} ai,bi ( 1<=ai 1<=a_{i} 1<=ai , bi<=n b_{i}<=n bi<=n , ai≠bi a_{i}≠b_{i} ai≠bi ). It is guaranteed that given graph is a tree.

输出格式：

In the first line print one integer number — maximal possible answer.

In the next n−1 n-1 n−1 lines print the operations in order of their applying in format ai,bi,ci a_{i},b_{i},c_{i} ai,bi,ci , where ai,bi a_{i},b_{i} ai,bi — pair of the leaves that are chosen in the current operation ( 1<=ai 1<=a_{i} 1<=ai , bi<=n b_{i}<=n bi<=n ), ci c_{i} ci ( 1<=ci<=n 1<=c_{i}<=n 1<=ci<=n , ci=ai c_{i}=a_{i} ci=ai or ci=bi c_{i}=b_{i} ci=bi ) — choosen leaf that is removed from the tree in the current operation.

See the examples for better understanding.

输入输出样例

输入样例#1：

3
1 2
1 3

输出样例#1：

3
2 3 3
2 1 1

输入样例#2：

输出样例#2：

Solution：

　　贪心+树的直径。

　　dfs处理出树的直径，然后先删去非直径上的分枝的叶子节点，再删直径。

　　树的直径一定是树上最长的一条简单路径，然后每次删掉非直径上的叶子节点的最远距离，一定是该节点与直径两端点中的某一个搭配出的最长距离，证明就一句话，不可能存在两个都是非直径上的叶子节点的路径超过直径的长度，画图或者脑补，其实蛮简单的贪心，就是难想到。

　　具体实现时，两遍dfs处理出直径，再dfs一遍处理出各节点到直径两端的距离，直径上的节点对答案的总贡献直接等差数列求和，非直径上的点直接累加到直径两段距离的最大值，然后输出方案，我的做法是将非直径上的节点和直径两端点的搭配都压入堆中，以距离为关键字，每次弹出就输出方案，最后只剩直径时就是固定一端依次删另一端就好了。

代码：

#include<bits/stdc++.h>
#define il inline
#define ll long long
#define For(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define Bor(i,a,b) for(int (i)=(b);(i)>=(a);(i)--)
using namespace std;
const int N=4e5+7;
int n,to[N],net[N],h[N],cnt;
int tp[N],q[N],tot,maxn;
ll dis1[N],dis2[N],ans;
bool vis[N];
struct node{
    int u,v;
    ll d;
    node(int a=0,int b=0,ll c=0){u=a;v=b;d=c;}
    bool operator<(const node &a)const {return d<a.d;}
};
priority_queue<node>Q;

il int gi(){
    int a=0;char x=getchar();
    while(x<''0''||x>''9'')x=getchar();
    while(x>=''0''&&x<=''9'')a=(a<<3)+(a<<1)+x-48,x=getchar();
    return a;
}

il void add(int u,int v){to[++cnt]=v,net[cnt]=h[u],h[u]=cnt;}

il void dfs1(int u,int lst){
    for(int i=h[u];i;i=net[i])
        if(!vis[to[i]]) vis[to[i]]=1,dfs1(to[i],lst+1),vis[to[i]]=0;
    if(lst>maxn) q[tot=1]=u,maxn=lst;
}

il void dfs2(int u,int lst){
    for(int i=h[u];i;i=net[i])
        if(!vis[to[i]]) tp[lst]=to[i],vis[to[i]]=1,dfs2(to[i],lst+1),vis[to[i]]=0;
    if(lst>tot) {
        tot=lst;
        For(i,2,lst) q[i]=tp[i];
    }
}

il void dfs3(int u,ll *a){
    for(int i=h[u];i;i=net[i])
        if(!vis[to[i]]) a[to[i]]=a[u]+1,vis[to[i]]=1,dfs3(to[i],a),vis[to[i]]=0;
}

int main(){
    n=gi();
    int u,v;
    For(i,1,n-1) u=gi(),v=gi(),add(u,v),add(v,u);
    vis[1]=1,dfs1(1,0),tot=0,vis[1]=0,vis[q[1]]=1,dfs2(q[1],2),tot--;
    dfs3(q[1],dis1),vis[q[1]]=0,vis[q[tot]]=1,dfs3(q[tot],dis2);
    For(i,1,tot) vis[q[i]]=1;
    ans=1ll*tot*(tot-1)/2;
    For(i,1,n)
        if(!vis[i])ans+=max(dis1[i],dis2[i]),Q.push(node(q[1],i,dis1[i])),Q.push(node(q[tot],i,dis2[i]));
    printf("%lld\n",ans);
    while(!Q.empty()){
        node a=Q.top();Q.pop();
        if(!vis[a.v]) printf("%d %d %d\n",a.u,a.v,a.v),vis[a.v]=1;
    }
    Bor(i,2,tot) printf("%d %d %d\n",q[1],q[i],q[i]);
    return 0;
}

CF914G Sum the Fibonacci FWT、子集卷积

传送门

一道良心的练习 FWT 和子集卷积的板子……

具体来说就是先把所有满足 $s_a & s_b = 0$ 的 $s_a \mid s_b$ 的值用子集卷积算出来，将所有 $s_a \oplus s_b$ 用 xor 卷积算出来，把斐波那契数代进去，然后将三个数组 and 卷积，最后取 $2^i (i \in Z)$ 的位置的答案的和

#include<bits/stdc++.h>
//this code is written by Itst
using namespace std;

int read(){
	int a = 0; char c = getchar();
	while(!isdigit(c)) c = getchar();
	while(isdigit(c)){
		a = a * 10 + c - 48;
		c = getchar();
	}
	return a;
}

const int _ = (1 << 17) + 3 , MOD = 1e9 + 7;
#define lowbit(x) (x & (-x))
int fib[_] , arr[_] , cnt1[_] , Or[18][_] , ansOr[_] , tmp[_] , And[_] , Xor[_] , N;

void orFWT(int *arr , long long tp){
	for(int i = 0 ; i < 17 ; ++i)
		for(int j = 0 ; j < 1 << 17 ; j += 1 << (i + 1))
			for(int k = 0 ; k < 1 << i ; ++k)
				arr[(1 << i) + j + k] = (arr[(1 << i) + j + k] + tp * arr[j + k] + MOD) % MOD;
}

void andFWT(int *arr , long long tp){
	for(int i = 0 ; i < 17 ; ++i)
		for(int j = 0 ; j < 1 << 17 ; j += 1 << (i + 1))
			for(int k = 0 ; k < 1 << i ; ++k)
				arr[j + k] = (arr[j + k] + tp * arr[(1 << i) + j + k] + MOD) % MOD;
}

void xorFWT(int *arr , long long tp){
	for(int i = 0 ; i < 17 ; ++i)
		for(int j = 0 ; j < 1 << 17 ; j += 1 << (i + 1))
			for(int k = 0 ; k < 1 << i ; ++k){
				int x = arr[j + k] , y = arr[(1 << i) + j + k];
				arr[j + k] = (x + y) % MOD;
				arr[(1 << i) + j + k] = (x - y + MOD) % MOD;
				if(tp == -1){
					if(arr[j + k] & 1) arr[j + k] += MOD;
					arr[j + k] >>= 1;
					if(arr[(1 << i) + j + k] & 1) arr[(1 << i) + j + k] += MOD;
					arr[(1 << i) + j + k] >>= 1;
				}
			}
}

void init(){
	for(int i = 1 ; i < 1 << 17 ; ++i)
		cnt1[i] = cnt1[i - lowbit(i)] + 1;
	fib[1] = 1;
	for(int i = 2 ; i < 1 << 17 ; ++i)
		fib[i] = (fib[i - 1] + fib[i - 2]) % MOD;
}

int main(){
#ifndef ONLINE_JUDGE
	freopen("in","r",stdin);
	//freopen("out","w",stdout);
#endif
	init();
	N = read();
	for(int i = 1 ; i <= N ; ++i){
		int p = read();
		++arr[p]; ++Or[cnt1[p]][p];
	}
	memcpy(And , arr , sizeof(arr)); memcpy(Xor , arr , sizeof(arr));
	for(int i = 0 ; i <= 17 ; ++i)
		orFWT(Or[i] , 1);
	for(int i = 0 ; i <= 17 ; ++i){
		memset(tmp , 0 , sizeof(tmp));
		for(int j = 0 ; j <= i ; ++j)
			for(int k = 0 ; k < 1 << 17 ; ++k)
				tmp[k] = (tmp[k] + 1ll * Or[j][k] * Or[i - j][k]) % MOD;
		orFWT(tmp , -1);
		for(int k = 0 ; k < 1 << 17 ; ++k)
			if(cnt1[k] == i)
				ansOr[k] = tmp[k];
	}
	xorFWT(Xor , 1);
	for(int i = 0 ; i < 1 << 17 ; ++i)
		Xor[i] = 1ll * Xor[i] * Xor[i] % MOD;
	xorFWT(Xor , -1);
	for(int i = 0 ; i < 1 << 17 ; ++i){
		ansOr[i] = 1ll * ansOr[i] * fib[i] % MOD;
		And[i] = 1ll * And[i] * fib[i] % MOD;
		Xor[i] = 1ll * Xor[i] * fib[i] % MOD;
	}
	andFWT(ansOr , 1); andFWT(And , 1); andFWT(Xor , 1);
	for(int i = 0 ; i < 1 << 17 ; ++i)
		And[i] = 1ll * ansOr[i] * And[i] % MOD * Xor[i] % MOD;
	andFWT(And , -1);
	int ans = 0;
	for(int i = 1 ; i < 1 << 17 ; i <<= 1)
		ans = (ans + And[i]) % MOD;
	cout << ans;
	return 0;
}

关于[CF930E]/[CF944G]Coins Exhibition的问题我们已经讲解完毕，感谢您的阅读，如果还想了解更多关于CF1039E Summer Oenothera Exhibition 根号分治，LCT，ST表、CF632E Thief in a Shop 和 CF958F3 Lightsabers (hard)、CF911F Tree Destruction、CF914G Sum the Fibonacci FWT、子集卷积等相关内容，可以在本站寻找。

本文标签：