题解：P11410 闪耀之塔

这题首先考虑使

\sum_{i=1}^{2^n-1} f(i)

最大，因为第

i

层节点

j

的贡献为

i \times val_j

所以可以贪心将大的数排在深度大的位置，也就是第

i

层任意放

[2^{i-1},2^i-1]

范围内的数。

其次考虑让

f(p)

最大，因为每层的数可以任意放，所以若第

i

层要放

j

个数那一定是放

[2^i-j,2^i-1]

这些数，可以列出一个 dp 式子，设

dp_i

为第

i

层放的数的总和，假如第

i

层放了

j

个数，第

i + 1

层放的数为

2 \times j

个数，发现第

i

层放的

j

个数为

[2^i-j,2^i-1]

这些数，而

i + 1

层放的

2 \times j

个数就为

[2^{i+1}-j \times 2,2^{i+1}-1]

发现转移式子为

dp_{i+1} = dp_{i} \times 4 + j

，

j

为第

i

层放的数量。但这东西显然过不了，考虑优化，这个 dp 显然可以矩阵优化，于是最后的时间复杂度为

O(q\log^3n)

。

代码

CPP

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
long long n,q,k;
string w;
struct node{
	long long a[5][5];
}a,d;
long long ksm(long long i,long long j)
{
	long long ans=1;
	while(j)
	{
		if(j%2==1) ans=(ans*i)%mod;
		i=(i*i)%mod;
		j/=2;
	}
	return ans;
}
node cf(node i,node j)
{
	node z;
	for(int ii=1;ii<=3;++ii)
		for(int jj=1;jj<=3;++jj)
			z.a[ii][jj]=0;
	for(int ii=1;ii<=3;++ii)
		for(int jj=1;jj<=3;++jj)
			for(int zz=1;zz<=3;++zz)
				z.a[ii][jj]=(z.a[ii][jj]+i.a[ii][zz]*j.a[zz][jj])%mod;
	return z;
}
long long ksm1(long long j)
{
	while(j)
	{
		if(j%2==1) a=cf(a,d);
		j/=2;
		d=cf(d,d);
	}
	return a.a[1][1];
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>q;
	for(int i=1;i<=q;++i)
	{
		cin>>k>>w;
		d.a[1][1]=1;
		d.a[1][2]=0;
		d.a[1][3]=0;
		d.a[2][1]=4;
		d.a[2][2]=4;
		d.a[2][3]=0;
		d.a[3][1]=1;
		d.a[3][2]=1;
		d.a[3][3]=2;
		a.a[1][1]=a.a[1][2]=(ksm(2,k)-1+mod)%mod;
		a.a[1][3]=1;
		for(int j=1;j<=3;++j)
			a.a[2][j]=a.a[3][j]=0;
		cout<<ksm1(n-k)<<'\n';
	}
	return 0; 
}

题解：P11410 闪耀之塔

文章操作

代码

相关推荐

评论

题解：P11410 闪耀之塔