2020.7.21集训

prime

description

对于给定的$n,p$n,p，其中$p$p是质数，分别求$i\times n,i\in[1,n]$i×n,i∈[1,n]在模$p$p意义下的逆元
$1\leq n<p\leq 3\times 10^6$1≤n<p≤3×106

solution
朴素的$O(n\log n)$O(nlogn)做法显然是不太行的
考虑分解一下
$inv(in)=inv(i)inv(n)$inv(in)=inv(i)inv(n)
所以我们只需要求$1$1到$n$n的逆元就可以了
这个东西可以$O(n)$O(n)递推做，左转洛谷乘法逆元模板

#include <bits/stdc++.h>
using namespace std;

# define Rep(i,a,b) for(int i=a;i<=b;i++)
# define _Rep(i,a,b) for(int i=a;i>=b;i--)
# define RepG(i,u) for(int i=head[u];~i;i=e[i].next)

typedef long long ll;

const int N=3e6+5;

template<typename T> void read(T &x){
   x=0;int f=1;
   char c=getchar();
   for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
   for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+c-'0';
    x*=f;
}

int n,p;
int inv[N];

int main()
{
	freopen("prime.in","r",stdin);
	freopen("prime.out","w",stdout);
	read(n),read(p);
	inv[1]=1;
	Rep(i,2,n)inv[i]=p-1ll*p/i*inv[p%i]%p;
	Rep(i,1,n)printf("%d\n",1ll*inv[i]*inv[n]%p);
	return 0;	
}

color

description
有一个编号$[0,n]$[0,n]的数列
$q$q次操作
1 x y c表示把$[x,y]$[x,y]中的数变成$c$c，其中$c\leq k$c≤k
2 x y表示查询$[x,y]$[x,y]中有多少个不同的数

$n,q\leq 5\times 10^5,k\leq 60$n,q≤5×105,k≤60

solution
朴素做法就是线段树维护60个数的信息
考虑优化
我们发现$k$k非常的小
所以我们可以把他们状压一下
然后这题就没了
吐槽样例出锅

#include <bits/stdc++.h>
using namespace std;

# define Rep(i,a,b) for(int i=a;i<=b;i++)
# define _Rep(i,a,b) for(int i=a;i>=b;i--)
# define RepG(i,u) for(int i=head[u];~i;i=e[i].next)

typedef long long ll;

const int N=5e5+5;

template<typename T> void read(T &x){
   x=0;int f=1;
   char c=getchar();
   for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
   for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+c-'0';
    x*=f;
}

int n,k,q;

struct node{
	int tag;
	ll bit;
}seg[N<<2];

# define lc (u<<1)
# define rc (u<<1|1)

void pushup(int u){
	seg[u].bit=seg[lc].bit|seg[rc].bit;	
}

void pushdown(int u){
	seg[lc].bit|=1ll<<seg[u].tag;
	seg[lc].tag=seg[u].tag;
	seg[rc].bit|=1ll<<seg[u].tag;
	seg[rc].tag=seg[u].tag;	
	seg[u].tag=0;
}

void update(int u,int l,int r,int ql,int qr,int k){
	if(l>=ql&&r<=qr){
		seg[u].bit|=1ll<<k;
		seg[u].tag=k;
		return;	
	}
	if(seg[u].tag)pushdown(u);
	int mid=l+r>>1;
	if(ql<=mid)update(lc,l,mid,ql,qr,k);
	if(qr>mid)update(rc,mid+1,r,ql,qr,k);
	pushup(u);
}

ll query(int u,int l,int r,int ql,int qr){
	if(l>=ql&&r<=qr)return seg[u].bit;
	if(seg[u].tag)pushdown(u);
	int mid=l+r>>1;
	if(qr<=mid)return query(lc,l,mid,ql,qr);
	if(ql>mid)return query(rc,mid+1,r,ql,qr);
	return query(lc,l,mid,ql,qr)|query(rc,mid+1,r,ql,qr);
}

int bitcount(ll x){
	int res=0;
	while(x){
		if(x&1)res++;
		x>>=1;	
	}
	return res;	
}

int main()
{
	freopen("color.in","r",stdin);
	freopen("color.out","w",stdout);
	read(n),read(k),read(q);	
	Rep(i,1,q){
		char opt[10];
		int x,y,c;
		scanf("%s",opt);
		read(x),read(y);
		if(opt[0]=='C')read(c),update(1,0,n,x,y,c+1);
		else printf("%d\n",bitcount(query(1,0,n,x,y)));	
	}
	return 0;
}

threefour

description
有一棵以1为根的$n$n个节点的树
定义无序数对$(a,b,c,d,z)$(a,b,c,d,z)如果满足

• $a,b,c,d,lca(a,b),lca(c,d),lca(lca(a,b),lca(c,d))$a,b,c,d,lca(a,b),lca(c,d),lca(lca(a,b),lca(c,d))互不相同
• $z$z是上面7个点的祖先

则称$(a,b,c,d,z)$(a,b,c,d,z)是不三不四的
问给定的树种，有多少个不三不四数对

答案模$1234567891$1234567891

$n\leq 5\times10^5$n≤5×105

solution

我们发现，树的形态一定固定的
大家手画一下图就可以看出来

考虑树形dp

用$f[u]$f[u]表示在$u$u的节点中选出两个点使得这两个点的lca为$u$u的方案树
$f[u]=\sum_{v_1}\sum_{v_2}siz[v_1]siz[v_2]$f[u]=v1​∑​v2​∑​siz[v1​]siz[v2​]
记$sumf[u]$sumf[u]表示在$u$u和$u$u子树中的$f$f的和
设$g[u]$g[u]表示以$u$u为$lca(lca(a,b),lca(c,d))$lca(lca(a,b),lca(c,d))时的答案
$g[u]=(dep[u]-1)\sum_{v_1}\sum_{v_2}sumf[v_1]sumf[v_2]$g[u]=(dep[u]−1)v1​∑​v2​∑​sumf[v1​]sumf[v2​]

答案就是$\sum g[i]$∑g[i]

这样我们得到了一个$O(n^2)$O(n2)的做法
可以得到50分

考虑如何进一步优化
我们稍微改造一下上面的转移方程

$2f[u]=\sum_v siz[v](siz[u]-1-siz[v])$2f[u]=v∑​siz[v](siz[u]−1−siz[v])
$2g[u]=\sum_v sumf[v](sumf[u]-f[u]-sumf[v])$2g[u]=v∑​sumf[v](sumf[u]−f[u]−sumf[v])

然后我们就可以$O(n)$O(n)做这个东西了
因为是在模意义下，所以要乘上2的逆元

#include <bits/stdc++.h>
using namespace std;

# define Rep(i,a,b) for(int i=a;i<=b;i++)
# define _Rep(i,a,b) for(int i=a;i>=b;i--)
# define RepG(i,u) for(int i=head[u];~i;i=e[i].next)

typedef long long ll;

const int N=5e5+5;
const int mod=1234567891;

template<typename T> void read(T &x){
   x=0;int f=1;
   char c=getchar();
   for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
   for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+c-'0';
    x*=f;
}

# define int long long

int n;
int head[N],cnt;
int dep[N],siz[N],f[N],g[N],sumf[N];
int inv;
int ans;

struct Edge{
	int to,next;	
}e[N<<1];

void add(int x,int y){
	e[++cnt]=(Edge){y,head[x]},head[x]=cnt;	
}

int Qpow(int base,int ind){
	int res=1;
	while(ind){
		if(ind&1)res=res*base%mod;
		base=base*base%mod;
		ind>>=1;
	}
	return res;
}

void dfs1(int u,int fa){
	siz[u]=1;
	dep[u]=dep[fa]+1;
	RepG(i,u){
		int v=e[i].to;
		if(v==fa)continue;
		dfs1(v,u);
		siz[u]+=siz[v];	
		sumf[u]+=sumf[v];
		sumf[u]%=mod;
	}
	RepG(i,u){
		int v=e[i].to;
		if(v==fa)continue;
		f[u]+=siz[v]*(siz[u]-1-siz[v]+mod+mod)%mod;
		f[u]%=mod;	
	}
	f[u]=f[u]*inv%mod;
	sumf[u]+=f[u];
	sumf[u]%=mod;
}

void dfs2(int u,int fa){
	RepG(i,u){
		int v=e[i].to;
		if(v==fa)continue;
		dfs2(v,u);
		g[u]+=(dep[u]-1)*sumf[v]%mod*(sumf[u]-f[u]-sumf[v]+mod+mod)%mod;
		g[u]%=mod;
	}
	g[u]=g[u]*inv%mod;
}

signed main()
{
	freopen("threefour.in","r",stdin);
	freopen("threefour.out","w",stdout);
	memset(head,-1,sizeof(head));
	read(n);
	Rep(i,1,n-1){
		int x,y;
		read(x),read(y);
		add(x,y),add(y,x);
	}
	inv=Qpow(2,mod-2);
	dfs1(1,0);
	dfs2(1,0);
	Rep(i,1,n)ans+=g[i],ans%=mod;
	printf("%lld\n",ans);
	return 0;
}