GXOI/GZOI2019 选做

Posted on | Edited on | Views:

广西/贵州 $OI$ .

题面

Day 1
Day 2

与或和

  • 显然可以每一位分开做.
  • 或就是用总子矩阵数目减去全 $0$ 子矩阵数目.与就是全 $1$ 子矩阵数目.单调栈经典问题.
  • 时间复杂度 $O(32n^2)​$ .
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read()
{
	ll out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int P=1e9+7,inv2=(P+1)>>1;
inline int add(int a,int b)
{
	return (a + b) % P;
}
inline int mul(int a,int b)
{
	return 1LL * a * b % P;
}
const int MAXN=1e3+10;
int n,a[MAXN][MAXN];
int d[MAXN][MAXN];
int ansand=0,ansor=0;
int stk[MAXN],tp;
int calc(int k,int v)//submatrix all of v
{
#define val ((a[i][j]>>k)&1)
	for(int i=1;i<=n;++i)
	{
		for(int j=1;j<=n;++j)
		{
			if(val!=v)
				d[i][j]=0;
			else
				d[i][j]=d[i-1][j]+1;
		}
	}
	int s,res=0;
	for(int i=1;i<=n;++i)
	{
		tp=0;
		s=0;
		for(int j=1;j<=n;++j)
		{
			s=add(s,d[i][j]);
			while(tp && d[i][stk[tp]]>=d[i][j])
			{
				int del=mul(add(stk[tp],P-stk[tp-1]),add(d[i][stk[tp]],P-d[i][j]));
				s=add(s,P-del);
				--tp;
			}
			res=add(res,s);
			stk[++tp]=j;
		}
	}
	return res;
}
int main()
{
	n=read();
	for(int i=1;i<=n;++i)
		for(int j=1;j<=n;++j)
			a[i][j]=read();
	int tot=mul(n,n+1);
	tot=mul(tot,inv2);
	tot=mul(tot,tot);
	for(int k=0;k<31;++k)
	{
		int tmpand=calc(k,1);
		tmpand=mul(tmpand,1<<k);
		ansand=add(ansand,tmpand);
		int tmpor=add(tot,P-calc(k,0));
		tmpor=mul(tmpor,1<<k);
		ansor=add(ansor,tmpor);
	}
	cout<<ansand<<' '<<ansor<<endl;
	return 0;
}

宝牌一大堆

  • 怎么又是 $mahjong$ …是不是可以专门出一类 麻将 $dp$ 啊.
  • 七对子和国士无双可以单独做.七对子可以 $dp$ , $g(i,j)$ 表示考虑前 $i$ 种牌,组成 $j$ 个对子的最大得分.国士无双可以大力枚举一下哪张幺九牌有两张.
  • 对于普通的 $3\times 4+2$ 的胡牌,把牌搞上标号,使得顺子的标号是连续的.记 $f[i][j][k][l][m][n]$ 表示考虑了前 $i$ 种牌,形成了 $j$ 个面子, $k$ 个雀头, $i-2,i-1,i$ 已经选了 $l,m,n$ 个时,前 $i-3$ 种牌能获得的最大得分.
  • 转移时枚举一下 $i$ 这张牌不选/成刻子/成杠子/与 $i-2,i-1$ 成顺子的几种情况即可,注意判断合法性.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
ll g[35][35];
ll f[35][5][2][5][5][5],ans;
int a[35],c[5][5],d[35];
bool shunend[]={0,0,0,1,1,1,1,1,1,1,0,0,1,1,1,1,1,1,1,0,0,1,1,1,1,1,1,1,0,0,0,0,0,0,0};
void init()
{
	memset(f,0,sizeof f);
	memset(g,0,sizeof g);
	ans=0;
	for(int i=1;i<=34;++i)
		d[i]=0,a[i]=4;
}
// 1m 2m ... 9m 1p 2p ... 9p 1s 2s ... 9s E S W N Z B F
int id(char s[])
{
	if(s[0]=='E')
		return 28;
	if(s[0]=='S')
		return 29;
	if(s[0]=='W')
		return 30;
	if(s[0]=='N')
		return 31;
	if(s[0]=='Z')
		return 32;
	if(s[0]=='B')
		return 33;
	if(s[0]=='F')
		return 34;
	if(s[1]=='m')
		return s[0]-'0';
	if(s[1]=='p')
		return s[0]-'0'+9;
	if(s[1]=='s')
		return s[0]-'0'+18;
	return 0;
}
void upd(ll &x,ll y)
{
	if(y>x)
		x=y;
}
ll dora(int idx,int cnt)
{
	if(d[idx])
		return 1LL<<cnt;
	return 1LL;
}
ll MaHu()
{
	ll res=0;
	f[1][0][0][0][0][0]=1;
	for(int i=1;i<=34;++i)
	for(int j=0;j<=4;++j)
	for(int k=0;k<=1;++k)
	for(int l=0;l<=4;++l)
	for(int m=0;m<=4;++m)
	for(int n=0;n<=4;++n)
	{
		ll cur=f[i][j][k][l][m][n];
		if(!cur)
			continue;
		if(i<34)
			upd(f[i+1][j][k][m][n][0],cur*(i>2?c[a[i-2]][l]*dora(i-2,l):1));//give up
		if(j<4 && a[i]-n>=3)
			upd(f[i][j+1][k][l][m][n+3],cur);//kezi
		if(j<4 && a[i]-n>=4)
			upd(f[i][j+1][k][l][m][n+4],cur);//gangzi
		if(j<4 && shunend[i] && a[i]-n && a[i-1]-m && a[i-2]-l)
			upd(f[i][j+1][k][l+1][m+1][n+1],cur);//shunzi
		if(!k && a[i]-n>=2)
			upd(f[i][j][k+1][l][m][n+2],cur);
		if(i==34 && j==4 && k==1)
		{
			ll s=cur*c[a[i]][n]*c[a[i-1]][m]*c[a[i-2]][l];
			s*=dora(i,n)*dora(i-1,m)*dora(i-2,l);
			upd(res,s);
		}
	}
	return res;
}
ll QiDuizi()
{
	g[0][0]=1;
	for(int i=1;i<=34;++i)
		for(int j=0;j<=7;++j)
		{
			if(!g[i-1][j])
				continue;
			upd(g[i][j],g[i-1][j]);
			if(j<7)
				upd(g[i][j+1],g[i-1][j]*c[a[i]][2]*dora(i,2));
		}
	return g[34][7]*7;
}
int yao[13]={1,9,10,18,19,27,28,29,30,31,32,33,34};
ll GSWS()
{
	ll res=0;
	for(int i=0;i<13;++i)
	{
		if(a[yao[i]]==0)
			return 0;
		if(a[yao[i]]==1)
			continue;
		ll tmp=c[a[yao[i]]][2]*dora(yao[i],2);
		for(int j=0;j<13;++j)
		{
			if(i==j)
				continue;
			tmp*=c[a[yao[j]]][1]*dora(yao[j],1);
		}
		upd(res,tmp);
	}
	return res*13;
}
int main()
{
	for(int i=0;i<=4;++i)
		c[i][0]=1;
	for(int i=1;i<=4;++i)
		for(int j=1;j<=4;++j)
			c[i][j]=c[i-1][j]+c[i-1][j-1];
	int T=read();
	while(T--)
	{
		init();
		char s[5];
		while(1)
		{
			scanf("%s",s);
			int x=id(s);
			if(x)
				--a[x];
			else
				break;
		}
		while(1)
		{
			scanf("%s",s);
			int x=id(s);
			if(x)
				d[x]=1;
			else
				break;
		}
		upd(ans,MaHu());
		upd(ans,QiDuizi());
		upd(ans,GSWS());
		printf("%lld\n",ans);
	}
	return 0;
}

特技飞行

  • 无论怎样决策,所有交点的位置是确定的.所以 $c$ 的贡献可以和 $a,b$ 分开算.
  • 所有合法决策最值,一定是一个使 对向交换 的次数最多,另一个使 对向交换 的次数最少.
  • 计算 $a,b$ 的贡献时,交点的具体位置不重要,先只考虑 $y$ 的相对大小.
  • 对于最多的情况,我们可以在 每个 交点处都选择 对向交换 .因为每个交点其实就是二元组 $(y_0,y_1)$ 的一个逆序对产生的.那么将每个逆序对的 $y_1$ 都交换,最后就不会有逆序对(交换排序),即满足要求.
  • 对于最少的情况,可以发现对于 $y_1$ 中的每个置换,内部需要交换大小 $-1$ 次,各个置换独立,那么总交换次数为 $n-​$ 置换数目.找到的证明.
  • 再来算 $c$ 的贡献.可以把所有点按 $y_1$ 从大到小依次加入 $set$ 中,以 $y_0$ 为关键字,这样能产生交点的点在 $set$ 中是一个前缀部分,合法就计算交点,不合法时就跳出,加入下一个点.
  • 曼哈顿距离不太好搞,经典套路,转化成切比雪夫距离,就变成了问每个交点是否被一些矩形中的至少一个覆盖.
  • 把点加入 $kdtree$ 中,每个矩形给其中的点打一打标记就好了.也可以离线后扫描线+树状数组.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read()
{
	ll out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const double eps=1e-10;
int fcmp(double x)
{
	if(fabs(x)<=eps)
		return 0;
	return x>0?1:-1;
}
const int MAXN=5e5+10;
typedef pair<int,int> pii;
#define mp make_pair
int n,Y0[MAXN],Y1[MAXN],st,ed,is[MAXN],tot,id[MAXN],to[MAXN],k,vis[MAXN];
ll A,B,C;
double mn[MAXN][2],mx[MAXN][2];
int flag[MAXN],D,ch[MAXN][2],marked[MAXN];
// flag表示这个点以及其管辖的点都被标记了 marked表示这个点被标记了 
set<pii> s;
set<pii>::iterator it;
struct point
{
	double p[2];
	point(){p[0]=p[1]=0;}
	point(double x,double y){p[0]=x,p[1]=y;}
	bool operator < (const point &rhs) const
	{
		return p[D]==rhs.p[D]?p[D^1]<rhs.p[D^1]:p[D]<rhs.p[D];
	}
}a[MAXN];
bool cmp(int a,int b)
{
	return Y1[a]<Y1[b];
}
void pushup(int o,int x)
{
	for(int i=0;i<2;++i)
	{
		mn[o][i]=min(mn[o][i],mn[x][i]);
		mx[o][i]=max(mx[o][i],mx[x][i]);
	}
}
int BuildTree(int l,int r,int d)
{
	if(l>r)
		return 0;
	int mid=(l+r)>>1;
	D=d;
	nth_element(a+l,a+mid,a+r+1);
	int o=mid;
	for(int i=0;i<2;++i)
		mn[o][i]=mx[o][i]=a[o].p[i];
	if(l<=mid-1)
	{
		ch[o][0]=BuildTree(l,mid-1,d^1);
		pushup(o,ch[o][0]);
	}
	if(mid+1<=r)
	{
		ch[o][1]=BuildTree(mid+1,r,d^1);
		pushup(o,ch[o][1]);
	}
	return o;
}
void update(int x,int y,int r,int o)
{
	if(!o || flag[o] || x+r<mn[o][0] || x-r>mx[o][0] || y+r<mn[o][1] || y-r>mx[o][1])
		return;
	double mxd=0;
	mxd=max(mxd,fabs(x-mn[o][0]));
	mxd=max(mxd,fabs(x-mx[o][0]));
	mxd=max(mxd,fabs(y-mn[o][1]));
	mxd=max(mxd,fabs(y-mx[o][1]));
	if(fcmp(mxd-r)<=0)
	{
		flag[o]=1;
		return;
	}
	double curd=max(fabs(x-a[o].p[0]),fabs(y-a[o].p[1]));
	if(!marked[o] && fcmp(curd-r)<=0)
		marked[o]=1;
	update(x,y,r,ch[o][0]);
	update(x,y,r,ch[o][1]);
}
int dfs(int o)
{
	if(flag[o])
	{
		marked[o]=1;
		marked[ch[o][0]]=marked[ch[o][1]]=1;
		flag[ch[o][0]]=flag[ch[o][1]]=1;
	}
	int res=marked[o];
	if(ch[o][0])
		res+=dfs(ch[o][0]);
	if(ch[o][1])
		res+=dfs(ch[o][1]);
	return res;
}
int main()
{
	n=read(),A=read(),B=read(),C=read();
	st=read(),ed=read();
	for(int i=1;i<=n;++i)
		Y0[i]=read();
	for(int i=1;i<=n;++i)
		Y1[i]=read();
	for(int i=n;i>=1;--i)
	{
		for(it=s.begin();it!=s.end() && it->first < Y1[i];++it)
		{
			int j=it->second;
			double t=(double)(Y0[j]-Y0[i])/(Y1[i]-Y1[j]);
			double ox=(t*ed+st)/(t+1);
			double oy=(t*Y1[j]+Y0[j])/(t+1);
			double x=ox+oy,y=ox-oy;
			a[++tot]=point(x,y); 
		}
		s.insert(mp(Y1[i],i));
	}
	int rt=BuildTree(1,tot,0);
	k=read();
	for(int i=1;i<=k;++i)
	{
		int ox=read(),oy=read(),r=read();
		int x=ox+oy,y=ox-oy;
		update(x,y,r,rt);
	}
	ll ans=dfs(rt)*C;
	ll ans1=ans+tot*A;
	for(int i=1;i<=n;++i)
		id[i]=i;
	sort(id+1,id+1+n,cmp);
	ll rep=n;
	for(int i=1;i<=n;++i)
		if(!vis[i])
		{
			--rep;
			for(int j=i;!vis[j];j=id[j])
				vis[j]=1;
		}
	ll ans2=ans1+(tot-rep)*(B-A);
	if(ans1>ans2)
		swap(ans1,ans2);
	printf("%lld %lld\n",ans1,ans2);
	return 0;
}

逼死强迫症

  • 求必须用两块 $1\times 1$ 的方案,转化一下,设 $f_i$ 表示任意用砖,铺满前 $i$ 列的方案数, $g_i$ 表示只用 $1\times 2$ 的砖铺满前 $i$ 列的方案数.那么最后的答案就是 $f_n-g_n$ .
  • $g$ 的转移很简单, $g_i=g_{i-1}+g_{i-2},g_0=1,g_1=1​$ .
  • $f$ 的转移呢?多出来一列时,若不在这一列用 $1\times 1$ 的砖,那么方案数为 $f_{i-1}+f_{i-2}$ .
  • 若在这一列用 $1\times 1$ 的砖,那么为了填满前 $i$ 列,另外一块 $1\times 1$ 也必须用,并且只能放在第 $1\sim i-2​$ 列.
  • 若这两块砖中间还有偶数列,那么它们只能在同一行,否则,只能在不同的一行.看下面的图片感性理解:

  • 那么左边那块 $1\times 1$ 的左边只能用 $1\times 2$ 填满,方案数用 $g$ 计算,右边只能有 $1$ 种填法.
  • 枚举右边那块 $1\times 1$放在第 $1,2$ 行,左边那块 $1\times 1$ 放在第 $j$ 列.
  • 整理一下,就有 $f_i=f_{i-1}+f_{i-2}+2\times \sum_{j=1}^{i-2} g_{j-1}$ .
  • 边界有 $f_1=1,f_2=2$ .把 $g$ 的前缀和, $g,f$ 一起用矩阵快速幂优化转移即可.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int P=1e9+7;
inline int add(int a,int b)
{
	return (a + b) % P;
}
inline int mul(int a,int b)
{
	return 1LL * a * b % P;
}
struct matrix
{
	int v[6][6];
	matrix(){memset(v,0,sizeof v);}
	matrix operator * (const matrix &rhs) const
	{
		matrix res;
		for(int i=0;i<6;++i)
			for(int j=0;j<6;++j)
				for(int k=0;k<6;++k)
					res.v[i][j]=add(res.v[i][j],mul(v[i][k],rhs.v[k][j]));
		return res;
	}
};
matrix fpow(matrix a,int b)
{
	matrix res;
	for(int i=0;i<6;++i)
		res.v[i][i]=1;
	while(b)
	{
		if(b&1)
			res=res*a;
		a=a*a;
		b>>=1;
	}
	return res;
}
matrix trans,st;
void setv(int x,int y)
{
	trans.v[x][y]+=1;
}
void init()
{
	st.v[0][0]=5;
	st.v[1][0]=2;
	st.v[2][0]=3;
	st.v[3][0]=2;
	st.v[4][0]=1;
	st.v[5][0]=1;
}
int main()
{
	setv(0,0),setv(0,1),setv(0,4),setv(0,5),setv(0,4),setv(0,5);
	setv(1,0);
	setv(2,2),setv(2,3);
	setv(3,2);
	setv(4,3);
	setv(5,4),setv(5,5);
	int T=read();
	while(T--)
	{
		int n=read();
		if(n<=3)
		{
			if(n==1)
				cout<<0<<endl;
			else if(n==2)
				cout<<0<<endl;
			else if(n==3)
				cout<<2<<endl;
			continue;
		}
		init();
		st=fpow(trans,n-3)*st;
		printf("%d\n",add(st.v[0][0],P-st.v[2][0]));
	}
	return 0;
}

旅行者

  • 考虑将所有 感兴趣的城市 划分到两个集合 $A,B$ 中,从 $S$ 向 $A$ 中每个点连 $0$ 边,从 $B$ 中每个点向 $T$ 中连 $0$ 边.
  • 这样从 $S$ 到 $T$ 的最短路长度就是 $A$ 与 $B$ 中两两最短路的最小值.
  • 怎样划分才能使每对 感兴趣的城市 都被算入贡献中呢?
  • 考虑划分 $logn$ 轮,每一轮将二进制第 $i$ 位上为 $0$ 的点划入 $A$ 中,否则划入 $B$ 中.这样两个不同的城市在至少一轮中被划分进了不同的集合,一定能产生贡献.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf=1e18;
inline ll read()
{
	ll out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int MAXN=2e5+10,MAXM=7e5+10;
int ecnt,head[MAXN],to[MAXM],nx[MAXM],val[MAXM];
void addedge(int u,int v,int w)
{
	++ecnt;
	to[ecnt]=v;
	nx[ecnt]=head[u];
	val[ecnt]=w;
	head[u]=ecnt;
}
void init()
{
	ecnt=0;
	memset(head,0,sizeof head);
}
int n,m,k;
int city[MAXN],orghead[MAXN];
ll dis[MAXN];
bool vis[MAXN];
typedef pair<ll,int> pli;
#define mp make_pair
ll dij(int S,int T)
{
	for(int i=1;i<=n+2;++i)
	{
		dis[i]=inf;
		vis[i]=false;
	}	
	dis[S]=0;
	priority_queue<pli> q;
	q.push(mp(0,S));
	while(!q.empty())
	{
		int u=(q.top()).second;
		q.pop();
		if(vis[u])
			continue;
		vis[u]=true;
		for(int i=head[u];i;i=nx[i])
		{
			int v=to[i];
			if(dis[u]+val[i]<dis[v])
			{
				dis[v]=dis[u]+val[i];
				q.push(mp(-dis[v],v));
			}
		}
	}
	return dis[T];
}
int main()
{
	int Cases=read();
	while(Cases--)
	{
		init();
		n=read(),m=read(),k=read();
		for(int i=1;i<=m;++i)
		{
			int u=read(),v=read(),w=read();
			addedge(u,v,w);
		}
		for(int i=1;i<=k;++i)
			city[i]=read();
		int rounds=1+(int)log2(n);
		int S=n+1,T=n+2;
		ll ans=inf;
		for(int p=0;p<=rounds;++p)
		{
			for(int i=1;i<=k;++i)
				if((city[i]>>p)&1)
					orghead[i]=head[city[i]];
			for(int i=1;i<=k;++i)
				if((city[i]>>p)&1)
					addedge(city[i],T,0);
				else
					addedge(S,city[i],0);
			ans=min(ans,dij(S,T));
			head[S]=0;
			for(int i=1;i<=k;++i)
				if((city[i]>>p)&1)
					head[city[i]]=orghead[i];
			ecnt-=k;
		}
		printf("%lld\n",ans);
	}
	return 0;
}

旧词

  • 先来考虑 $k=1$ 的部分,做法是将 $lca$ 处 $dep$ 的贡献摊到这个点到根的路径上.
  • 具体来说将询问离线下来,按 $x$ 排序后就可以从小到大一个个加入点.每加入一个点的时候就把这个点到根的路径上点的权值都 $+1$ ,询问时就查询 $y$ 到根的路径上点的权值和.
  • 考虑拓展到 $k>1$ 的部分,沿用上面的思路,发现每次给路径上每个点权值 $+\ (dep_i^k-(dep_i-1)^k)$ 就好了.
  • 这样就可以使 $lca$ 的权值恰好被摊到路径上,查询时仍然查询路径权值和就好了.
  • 树剖+线段树维护一下,时间复杂度 $O(nlog^2n)$ .
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int P=998244353;
inline int add(int a,int b)
{
	return (a + b >= P)? (a + b - P) : (a + b);
}
inline int mul(int a,int b)
{
	return 1LL * a * b % P;
}
int fpow(int a,int b)
{
	int res=1;
	while(b)
	{
		if(b&1)
			res=mul(res,a);
		a=mul(a,a);
		b>>=1;
	}
	return res;
}
const int MAXN=5e4+10;
int n,k,Q;
int ecnt=0,head[MAXN],to[MAXN<<1],nx[MAXN<<1];
inline void addedge(int u,int v)
{
	++ecnt;
	to[ecnt]=v;
	nx[ecnt]=head[u];
	head[u]=ecnt;
}
int siz[MAXN],mxson[MAXN],top[MAXN],fa[MAXN],dep[MAXN],dfn[MAXN],rnk[MAXN],idx=0;
void dfs1(int u,int Fa)
{
	dep[u]=dep[Fa]+1;
	siz[u]=1;
	fa[u]=Fa;
	for(int i=head[u];i;i=nx[i])
	{
		int v=to[i];
		if(v==Fa)
			continue;
		dfs1(v,u);
		siz[u]+=siz[v];
		if(siz[v]>siz[mxson[u]])
			mxson[u]=v;
	}
}
void dfs2(int u,int tp)
{
	top[u]=tp;
	dfn[u]=++idx;
	rnk[idx]=u;
	if(mxson[u])
		dfs2(mxson[u],tp);
	for(int i=head[u];i;i=nx[i])
	{
		int v=to[i];
		if(v==fa[u] || v==mxson[u])
			continue;
		dfs2(v,v);
	}
}
struct SegTree
{
	struct node
	{
		int l,r;
		int sum,delta,tag;
	}Tree[MAXN<<2];
#define root Tree[o]
#define lson Tree[o<<1]
#define rson Tree[o<<1|1]
	void pushup(int o)
	{
		root.sum=add(lson.sum,rson.sum);
	}
	void modifiy(int o,int c)
	{
		root.tag=add(root.tag,c);
		root.sum=add(root.sum,mul(c,root.delta));
	}
	void pushdown(int o)
	{
		if(root.tag)
		{
			modifiy(o<<1,root.tag);
			modifiy(o<<1|1,root.tag);
			root.tag=0;
		}
	}
	void BuildTree(int o,int l,int r)
	{
		root.l=l,root.r=r;
		root.tag=0;
		root.sum=0;
		if(l==r)
		{
			root.delta=add(fpow(dep[rnk[l]],k),P-fpow(dep[rnk[l]]-1,k));
			return;
		}
		int mid=(l+r)>>1;
		BuildTree(o<<1,l,mid);
		BuildTree(o<<1|1,mid+1,r);
		root.delta=add(lson.delta,rson.delta);
	}
	void update(int o,int L,int R,int c)
	{
		int l=root.l,r=root.r;
		if(L<=l && r<=R)
		{
			modifiy(o,c);
			return;
		}
		if(l>R || L>r)
			return;
		int mid=(l+r)>>1;
		pushdown(o);
		if(L<=mid)
			update(o<<1,L,R,c);
		if(R>mid)
			update(o<<1|1,L,R,c);
		pushup(o);
	}
	int query(int o,int L,int R)
	{
		int l=root.l,r=root.r;
		if(L<=l && r<=R)
			return root.sum;
		if(l>R || L>r)
			return 0;
		int mid=(l+r)>>1;
		pushdown(o);
		int res=0;
		if(L<=mid)
			res=add(res,query(o<<1,L,R));
		if(R>mid)
			res=add(res,query(o<<1|1,L,R));
		return res;
	}
}T;
int ans[MAXN];
struct query
{
	int x,y,id;
	bool operator < (const query &rhs) const
	{
		return x<rhs.x;
	}
}q[MAXN];
void path_upd(int x)
{
	while(top[x]!=1)
	{
		T.update(1,dfn[top[x]],dfn[x],1);
		x=fa[top[x]];
	}
	T.update(1,dfn[top[x]],dfn[x],1);
}
int path_query(int x)
{
	int res=0;
	while(top[x]!=1)
	{
		res=add(res,T.query(1,dfn[top[x]],dfn[x]));
		x=fa[top[x]];
	}
	res=add(res,T.query(1,dfn[top[x]],dfn[x]));
	return res;
}
int main()
{
	n=read(),Q=read(),k=read();
	for(int i=2;i<=n;++i)
	{
		int f=read();
		addedge(f,i);
	}
	for(int i=1;i<=Q;++i)
	{
		q[i].x=read();
		q[i].y=read();
		q[i].id=i;
	}
	sort(q+1,q+1+Q);
	dfs1(1,0);
	dfs2(1,1);
	T.BuildTree(1,1,n);
	int lstx=0;
	for(int i=1;i<=Q;++i)
	{
		int x=q[i].x,y=q[i].y;
		for(int j=lstx+1;j<=x;++j)
			path_upd(j);
		ans[q[i].id]=path_query(y);
		lstx=x;
	}
	for(int i=1;i<=Q;++i)
		printf("%d\n",ans[i]);
	return 0;
}