P11410 闪耀之塔 题解

linjunye · 2025-08-17 14:41:54 · 题解

不错的题，这里给一个矩阵优化 DP 的做法。

首先我们看每一个点的贡献，容易发现第一层的点贡献是 1，第二层是 2，依次类推。

所以，第一层放 1，第二层放 2 和 3，第 k 层放 2^k 到 2^{k+1}-1 的数最优。

然后关注我们的查询。

我们发现，这个点的深度就是 k（我们定义第一个点的深度为 1），所以答案和这个点是什么不重要，重要的是它的深度。

那么，我们相当于选择一个 n-k+1 层的满二叉树进行放数。

设 dp_i 表示选择一个 n-i+1 层的满二叉树进行放数，不难得到递推式：dp_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。

注意到 \sum_{j=0}^{i-2}2^{2j} 也是可以递推的，预处理之后，你就拿到了 60 分。

接下来怎么做？

我们现在不得不定义一些东西了。

我们记 mm_i 表示 2^{2i}，递推式：mm_i=4mm_{i-1}

我们记 sum_i 表示 \sum_{j=0}^{i-2}2^{2j}，递推式：sum_i=sum_{i-1}+2^{2i-2}=sum_{i-1}+mm_{i-1}。

我们记 p_i 表示 2^{n-(i+1)+1}=2^{n-i}，递推式：p_i=p_{i-1}\times inv_2，其中 inv_2 表示 2 的逆元。

那么 dp_i 可以表示成：dp_i=2dp_{i-1}-sum_{i-1}+inv_{i-1}+1。

上述的递推式可以放在一个矩阵中进行转移，转移式子为：

时间复杂度：O(qV^3\log n)，其中 V 是矩阵大小，你可以认为 V=5。

代码：

#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;
}
/*

*/

如果还有不理解的，可以看一下 60 分暴力代码：

#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;
}
/*

*/