题解：P11410 闪耀之塔

Yesod · 2025-01-07 12:03:14 · 题解

这题首先考虑使 \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) 。

代码

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