自动搬运

查看原文

来自洛谷，原作者为

	linjunye AFO.

搬运于2025-08-24 23:07:06，当前版本为作者最后更新于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$。

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

$$\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(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;
}
/*

*/