P7155 题解

· · 题解

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

预处理，考虑 dp_{i,j,k} 表示按下 i 按钮对应子树，从 j 走到 k 的方案数。转移的时候先求前缀和，再分布转移（求出往右一步和往左一步的答案再合并）。总复杂度 O(n^4)。

对于查询，考虑也类似做。区别在于我们需要区分在按的编号最大的按钮前/后，且不需要记录某一个端点（显然，有一个端点在最大位置前后分别为 s,t），因此可以 O(n^3) 解决。最后枚举最大值合并即可。注意特判最大值是两端/不走动的情况。

总复杂度 O(n^4+qn^3)。

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