P7155 题解

考虑按按钮的序列，对其建笛卡尔树，尝试对该结构设计 dp。

预处理，考虑

dp_{i,j,k}

表示按下

i

按钮对应子树，从

j

走到

k

的方案数。转移的时候先求前缀和，再分布转移（求出往右一步和往左一步的答案再合并）。总复杂度

O(n^4)

。

对于查询，考虑也类似做。区别在于我们需要区分在按的编号最大的按钮前/后，且不需要记录某一个端点（显然，有一个端点在最大位置前后分别为

s,t

），因此可以

O(n^3)

解决。最后枚举最大值合并即可。注意特判最大值是两端/不走动的情况。

总复杂度

O(n^4+qn^3)

。

CPP

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e9+7;
inline void add(int &i,int j){
	i+=j;
	if(i>=mod) i-=mod;
}
inline int addv(int i,int j){
	i+=j;
	if(i>=mod) i-=mod;
	return i;
}
int qp(int a,int b){
	int ans=1;
	while(b){
		if(b&1) (ans*=a)%=mod;
		(a*=a)%=mod;
		b>>=1;
	}
	return ans;
}
int n,k,q;
bool g[65][65];
int f[65][65][65];
int fl[65][65][65],fr[65][65][65];
int dp1[65][65],dp2[65][65];
int dp1r[65][65],dp2l[65][65];
signed main(){
	cin>>n>>k>>q;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			char c; cin>>c;
			g[i][j]=c-'0'; 
		} 
	}
	for(int i=1;i<=k;i++){
		for(int x=1;x<=n;x++) for(int y=1;y<=n;y++) f[i][x][y]=f[i-1][x][y];
		for(int x=1;x<=n;x++) for(int y=1;y<=n;y++) for(int z=1;z<=n;z++) if(g[y][z]) add(fr[i-1][x][z],f[i-1][x][y]);
		for(int x=1;x<=n;x++) for(int y=1;y<=n;y++) for(int z=1;z<=n;z++) if(g[x][y]) add(fl[i-1][x][z],f[i-1][y][z]);
		for(int x=1;x<=n;x++) for(int y=1;y<=n;y++) for(int z=1;z<=n;z++) add(f[i][x][z],fr[i-1][x][y]*fl[i-1][y][z]%mod);
		for(int x=1;x<=n;x++) for(int y=1;y<=n;y++) add(f[i][x][y],fr[i-1][x][y]);
		for(int x=1;x<=n;x++) for(int y=1;y<=n;y++) add(f[i][x][y],fl[i-1][x][y]);
		for(int x=1;x<=n;x++) add(f[i][x][x],1);
	}
	while(q--){
		int bs,s,bt,t; cin>>bs>>s>>bt>>t;
		memset(dp1,0,sizeof(dp1));
		memset(dp1r,0,sizeof(dp1r));
		memset(dp2,0,sizeof(dp2));
		memset(dp2l,0,sizeof(dp2l));
		{
			for(int x=1;x<=n;x++) add(dp1[bs][x],fl[bs-1][s][x]);
			add(dp1[bs][s],1);
			for(int i=bs+1;i<=k;i++){
				for(int x=1;x<=n;x++) dp1[i][x]=dp1[i-1][x];
				for(int x=1;x<=n;x++) for(int y=1;y<=n;y++) if(g[x][y]) add(dp1r[i-1][y],dp1[i-1][x]);
				for(int x=1;x<=n;x++) for(int y=1;y<=n;y++) add(dp1[i][y],dp1r[i-1][x]*fl[i-1][x][y]%mod);
				for(int x=1;x<=n;x++) add(dp1[i][x],dp1r[i-1][x]);
			}
//			cout<<dp1[1][1]<<" "<<dp1[2][2]<<" "<<dp1[3][3]<<"\n";
		}
		{
			for(int x=1;x<=n;x++) add(dp2[bt][x],fr[bt-1][x][t]);
			add(dp2[bt][t],1);
			for(int i=bt+1;i<=k;i++){
				for(int x=1;x<=n;x++) dp2[i][x]=dp2[i-1][x];
				for(int x=1;x<=n;x++) for(int y=1;y<=n;y++) if(g[x][y]) add(dp2l[i-1][x],dp2[i-1][y]);
				for(int x=1;x<=n;x++) for(int y=1;y<=n;y++) add(dp2[i][x],dp2l[i-1][y]*fr[i-1][x][y]%mod);
				for(int x=1;x<=n;x++) add(dp2[i][x],dp2l[i-1][x]);
			}
		}
		int ans=0;
		for(int i=max(bs,bt)+1;i<=k;i++) for(int x=1;x<=n;x++) add(ans,dp1r[i-1][x]*dp2l[i-1][x]%mod);
		if(bs==bt) add(ans,(s==t));
		if(bs<bt) add(ans,dp1r[bt-1][t]);
		if(bs>bt) add(ans,dp2l[bs-1][s]);
		cout<<ans<<"\n";
	}
	return 0;
}

文章操作

相关推荐

评论

P7155 题解