专栏文章

P11410 闪耀之塔 题解

llinjunye
P11410题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mioadxou
此快照首次捕获于
2025/12/02 15:58
3 个月前
此快照最后确认于
2025/12/02 15:58
3 个月前
查看原文
不错的题，这里给一个矩阵优化 DP 的做法。
首先我们看每一个点的贡献，容易发现第一层的点贡献是 11，第二层是 22，依次类推。
所以，第一层放 11，第二层放 22 和 33，第 kk 层放 2k2^k 到 2k+1−12^{k+1}-1 的数最优。
然后关注我们的查询。
我们发现，这个点的深度就是 kk（我们定义第一个点的深度为 11），所以答案和这个点是什么不重要，重要的是它的深度。
那么，我们相当于选择一个 n−k+1n-k+1 层的满二叉树进行放数。
设 dpidp_i 表示选择一个 n−i+1n-i+1 层的满二叉树进行放数，不难得到递推式：dpi=2dpi−1−∑j=0i−2(2j)2+2n−i+1+1=2dpi−1−∑j=0i−222j+2n−i+1+1dp_i=2dp_{i-1}-\sum_{j=0}^{i-2}(2^j)^2+2^{n-i+1}+1=2dp_{i-1}-\sum_{j=0}^{i-2}2^{2j}+2^{n-i+1}+1。
注意到 ∑j=0i−222j\sum_{j=0}^{i-2}2^{2j} 也是可以递推的，预处理之后，你就拿到了 6060 分。
接下来怎么做？
我们现在不得不定义一些东西了。
我们记 mmimm_i 表示 22i2^{2i}，递推式：mmi=4mmi−1mm_i=4mm_{i-1}
我们记 sumisum_i 表示 ∑j=0i−222j\sum_{j=0}^{i-2}2^{2j}，递推式：sumi=sumi−1+22i−2=sumi−1+mmi−1sum_i=sum_{i-1}+2^{2i-2}=sum_{i-1}+mm_{i-1}。
我们记 pip_i 表示 2n−(i+1)+1=2n−i2^{n-(i+1)+1}=2^{n-i}，递推式：pi=pi−1×inv2p_i=p_{i-1}\times inv_2，其中 inv2inv_2 表示 22 的逆元。
那么 dpidp_i 可以表示成：dpi=2dpi−1−sumi−1+invi−1+1dp_i=2dp_{i-1}-sum_{i-1}+inv_{i-1}+1。
上述的递推式可以放在一个矩阵中进行转移，转移式子为：
[dpisumipimmi1]=[2−11010101000inv2000004000001]×[dpi−1sumi−1pi−1mmi−11]\begin{bmatrix}dp_i\\sum_i\\p_i\\mm_i\\1\end{bmatrix}=\begin{bmatrix}2&-1&1&0&1\\0&1&0&1&0\\0&0&inv_2&0&0\\0&0&0&4&0\\0&0&0&0&1\end{bmatrix}\times\begin{bmatrix}dp_{i-1}\\sum_{i-1}\\p_{i-1}\\mm_{i-1}\\1\end{bmatrix}
时间复杂度：O(qV3log⁡n)O(qV^3\log n)，其中 VV 是矩阵大小，你可以认为 V=5V=5。
代码：
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int M=5;
const int mod=1e9+7;
struct matrix{
	int n,a[M][M];
	matrix(int _n){
		n=_n;
		memset(a,0,sizeof(a));
	}
	void print(){
		for(int i=0;i<n;i++,cout<<"\n")
			for(int j=0;j<n;j++)
				cout<<a[i][j]<<" ";
		cout<<"\n";
		return;
	}
	friend matrix operator * (matrix a,matrix b){
		int n=a.n;
		matrix c(n);
		for(int k=0;k<n;k++)
			for(int i=0;i<n;i++)
				for(int j=0;j<n;j++)
					c.a[i][j]=(c.a[i][j]+a.a[i][k]*b.a[k][j])%mod;
		return c;
	}
	friend matrix operator ^ (matrix a,int b){
		int n=a.n;
		matrix z(n);
		for(int i=0;i<n;i++)z.a[i][i]=1;
		while(b){
			if(b&1)z=z*a;
			a=a*a;
			b>>=1;
		}
		return z;
	}
};
int ksm(int a,int b){
    int z=1;
    while(b){
        if(b&1)z=z*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return z;
}
int inv(int x){
    return ksm(x,mod-2);
}
const int inv2=(mod+1)/2;
int n,k,q;
string s;
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
    cin>>n>>q;
    matrix A(5),B(5),ans(5);
    B.a[0][0]=0;
    B.a[1][0]=0;
    B.a[2][0]=ksm(2,n);
    B.a[3][0]=1;
    B.a[4][0]=1;
    A.a[0][0]=2;A.a[0][1]=-1;A.a[0][2]=1;A.a[0][3]=0;A.a[0][4]=-1;
    A.a[1][0]=0;A.a[1][1]=1;A.a[1][2]=0;A.a[1][3]=1;A.a[1][4]=0;
    A.a[2][0]=0;A.a[2][1]=0;A.a[2][2]=inv2;A.a[2][3]=0;A.a[2][4]=0;
    A.a[3][0]=0;A.a[3][1]=0;A.a[3][2]=0;A.a[3][3]=4;A.a[3][4]=0;
    A.a[4][0]=0;A.a[4][1]=0;A.a[4][2]=0;A.a[4][3]=0;A.a[4][4]=1;
    while(q--){
        cin>>k;
        cin>>s;
        ans=A;
        ans=ans^(n-k+1);
        ans=ans*B;
        // ans.print();
        cout<<(ans.a[0][0]%mod+mod)%mod<<"\n";
    }
	return 0;
}
/*

*/
如果还有不理解的，可以看一下 6060 分暴力代码：
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=3000010;
const int mod=1e9+7;
const int INF=0x3f3f3f3f3f3f3f3f;
int n,q;
int dp[N];
int sum[N];
int ksm(int a,int b){
    int z=1;
    while(b){
        if(b&1)z=z*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return z;
}
int inv(int x){
    return ksm(x,mod-2);
}
int k;
string s;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        dp[i]=2*dp[i-1]-sum[i-1]+ksm(2,n-i+1)-1;
        dp[i]=(dp[i]%mod+mod)%mod;
        sum[i]=sum[i-1]+ksm(2,i-1)*ksm(2,i-1)%mod;
        sum[i]%=mod;
    }
    while(q--){
        cin>>k;
        cin>>s;
        cout<<dp[n-k+1]<<"\n";
    }
    return 0;
}
/*

*/

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...