12
13
2016
1

Hackerrank Fibonacci Numbers Tree

写完发现艹了标算。

英文题面先说题意,给一个树,每个节点有权值,初始为0,两个操作,一种是给定root和k,对于root子树中所有节点,将其权值加上Fib(D+k),D是其到root的距离,第二种是链求和。

很显然2操作可以拆成4条到根的链之后直接爆,考虑每个1操作对其子树中答案的贡献,可以发现是$\sum_{i=k}^{deep[x]-deep[root]+k}Fib_{i}$的形式。

有$\sum_{i=1}^{n}Fib_{i}=Fib_{i+2}-1$所以那个东西等价于$Fib_{deep[x]-deep[root]+k+2}-Fib_{k+1}$

$Fib_{k+1}$是一个常量,直接维护就好,前面那个东西,可以拆成两个矩阵相乘来做,把$k-deep[root]+2$修改的时候做,$deep[x]$查询的时候再处理。

修改时矩阵先处理好,总复杂度$O(nlog)$

 

#include<cstdio>
#define mo 1000000007
using namespace std;
int n,m,cnt;
int head[100005];
char s[2];
int deep[100005],dfn[100005],ed[100005],fa[100005],size[100005],top[100005],son[100005];
inline long long lread(){
    long long ret=0;char c=getchar();
    while((c>'9')||(c<'0'))c=getchar();
    while((c>='0')&&(c<='9'))ret=(ret<<1)+(ret<<3)+c-'0',c=getchar();
    return ret;
}
inline int read(){
    int ret=0;char c=getchar();
    while((c>'9')||(c<'0'))c=getchar();
    while((c>='0')&&(c<='9'))ret=(ret<<1)+(ret<<3)+c-'0',c=getchar();
    return ret;
}
struct mar{
    int a[2][2];
    mar operator +(const mar &k)const{
        mar ans;
        for(int i=0;i<2;i++)
            for(int j=0;j<2;j++)ans.a[i][j]=(a[i][j]+k.a[i][j])%mo;
        return ans;
    }
    mar operator *(const mar &t)const{
        mar ans;
        for(int i=0;i<2;i++)
            for(int j=0;j<2;j++)ans.a[i][j]=0;
        for(int i=0;i<2;i++)
        	for(int j=0;j<2;j++)
        		for(int k=0;k<2;k++)ans.a[i][j]=(ans.a[i][j]+1LL*a[i][k]*t.a[k][j])%mo;
        return ans;
    }
    mar pow(long long k){
    	mar ans,tmp;
    	for(int i=0;i<2;i++)
    		for(int j=0;j<2;j++)tmp.a[i][j]=a[i][j];
    	ans.a[0][1]=ans.a[1][0]=0;ans.a[1][1]=ans.a[0][0]=1;
    	for(;k;k>>=1,tmp=tmp*tmp)if(k&1)ans=ans*tmp;
    	return ans;
    }
    void clear(){a[0][1]=a[0][0]=a[1][0]=a[1][1]=0;}
}f,nf;
struct tree{
	mar m;
	int y;
}t[400005];
struct edge{
	int to,next;
}e[200005];
void add(int u,int v){e[++cnt]=(edge){v,head[u]};head[u]=cnt;}
void dfs(int root){
	size[root]=1;
	for(int i=head[root];i;i=e[i].next)if(e[i].to!=fa[root]){
		deep[e[i].to]=deep[root]+1;fa[e[i].to]=root;
		dfs(e[i].to);
		if(size[e[i].to]>size[son[root]])son[root]=e[i].to;
		size[root]+=size[e[i].to];
	}
}
void Dfs(int root){
	dfn[root]=++cnt;
	if(son[root]){top[son[root]]=top[root];Dfs(son[root]);}
	for(int i=head[root];i;i=e[i].next)if((son[root]!=e[i].to)&&(e[i].to!=fa[root]))top[e[i].to]=e[i].to,Dfs(e[i].to);
	ed[root]=cnt;
}
inline int lca(int u,int v){
	int U=top[u],V=top[v];
	while(U!=V){
		if(deep[U]<deep[V])v=fa[V],V=top[v];
		else u=fa[U],U=top[u];
	}
	return deep[u]>deep[v]?v:u;
}
#define lson index<<1
#define rson index<<1|1
#define mid ((l+r)>>1)
void pushdown(int index){
	t[lson].m=t[lson].m+t[index].m;
	t[rson].m=t[rson].m+t[index].m;
	t[lson].y=(t[lson].y+t[index].y)%mo;
	t[rson].y=(t[rson].y+t[index].y)%mo;
	t[index].m.clear();t[index].y=0;
}
inline tree query(int l,int r,int index,int k){
	if(l==r)return t[index];
	pushdown(index);
	if(k<=mid)return query(l,mid,lson,k);
	else return query(mid+1,r,rson,k);
}
void change(int l,int r,int index,int L,int R,mar M,int x){
	if((L<=l)&&(R>=r)){t[index].m=t[index].m+M,t[index].y=(t[index].y+x)%mo;return;}
	if(L<=mid)change(l,mid,lson,L,R,M,x);
	if(R>mid)change(mid+1,r,rson,L,R,M,x);
}
inline int Q(int k){
	tree tmp=query(1,n,1,dfn[k]);
	tmp.m=tmp.m*f.pow(deep[k]);
	int ans=tmp.m.a[1][0]-tmp.y;
	if(ans<0)ans+=mo;
	return ans;
}
int main(){
	n=read();m=read();
	f.a[0][1]=1;f.a[1][0]=1;f.a[1][1]=1;
	nf.a[0][0]=mo-1;nf.a[1][0]=1;nf.a[0][1]=1;
	for(int i=2;i<=n;i++){
		int u=read();
		add(u,i);add(i,u);
	}
	cnt=0;
	dfs(1);top[1]=1;Dfs(1);
	while(m--){
		scanf("%s",s);
		if(s[0]=='Q'){
			int x=read(),y=read(),l=lca(x,y),ans=0;
			ans=(Q(x)+Q(y)-Q(l))%mo;
			if(fa[l])ans=(ans-Q(fa[l]))%mo;
			if(ans<0)ans+=mo;
			printf("%d\n",ans);
		}else{
			int x=read();
			long long k=lread();int Tmp=f.pow(k+1).a[1][0];mar tmp;
			if(k-deep[x]+2<0)tmp=nf.pow(deep[x]-k-2);
			else tmp=f.pow(k-deep[x]+2);
			change(1,n,1,dfn[x],ed[x],tmp,Tmp);
		}
	}
}
Category: hackerrank | Tags: fib 树剖 矩阵乘法 | Read Count: 1435
Avatar_small
PSC Result 2022 Comi 说:
2022年9月03日 01:50

Government of the People’s Republic of Bangladesh, Directorate of Primary Education (DPE), is going to announce PSC Result 2022 in student wide on 30th December 2022 for all divisional Grade 5 exam result with Ebtedayee Result 2022 for annual final terminal examinations, The Primary School Certificate Examination Result 2022 will be announced for both of General and Madhrsah students in division wise to all education board known as Prathomik Somaponi Result 2022. PSC Result 2022 Comilla Board The DPE has successfully conducted the class 5th grade PSC and Ebtedayee Examination tests from 17th to 24th November 2022 under all education boards of Dhaka, Chittagong, Comilla, Rajshahi, Sylhet, Barisal, Jessore, Dinajpur and Madrasah Board, and the DPE Grade-5 exams are successfully conducted at all 7,194 centers across the country.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com