洛谷P7155 [USACO20DEC] Spaceship P 题解

题意：

Bessie 在一张含 \(n\) 个结点的有向图上遍历，站在某个结点上时，她必须按下自己手中 \(m\) 个按钮中处于激活状态的一个才能走向其他结点或终止遍历（不能原地等待）。初始时，所有按钮都处于激活状态，按下 \(i\) 号按钮时，\(i\) 号按钮变为非激活状态，所有编号小于 \(i\) 的按钮被激活。

给定 \(q\) 组形如 \((b_s,s,b_t,t)\) 的询问，求 Bessie 从 \(s\) 出发，第一步按 \(b_s\) 按钮，到 \(t\) 终止遍历，且最后一步按 \(b_t\) 按钮的遍历方案数（遍历顺序或按键不同，方案则不同）。

输入格式：

输入的第一行包含 \(n,m,q\)。

接下来 \(n\) 行长度为 \(n\) 的 \(01\) 串，表示图的邻接矩阵。

接下来 \(q\) 行 \((b_s,s,b_t,t)\) 询问，变量含义见题意。

输出格式：

对于每个询问，给出答案模 \(10^9 + 7\) 的值。

数据范围：

\(1 \le n,m,q \le 60\) 。

显然这 \(m\) 个按钮可以压成一个 \(2^m\) 的数。可以发现，每次按按钮，都不会使得数字变大。

而其中最特殊的情况就是按最高位的那个按钮，因为之后再怎么瞎按这一位都不会变成激活状态。

也就是说，最高的未激活的位能被重新激活当且仅当被更高的位激活了。

考虑设 \(f(h,i,j)\) 为从 \(i\) 出发走到 \(j\) ，且未激活按钮的最高位不超过 \(h\) 的方案数。

注意这里暂时没有钦定第一步/最后一步怎么按按钮。考虑转移。（下面 \(\uparrow\) 均表示增量）

如果当前按钮根本没有按到过 \(h\) ，那么 \[ f(h,i,j) \uparrow f(h-1,i,j) \]
否则枚举按了 \(h\) 的点 \(k\) （显然 \(k\) 是唯一的），那么 \[ f(h, i, j) \uparrow \sum_{(u, k),(k, v) \in E} f(h-1, i, u) f(h-1, v, j) \] 注意到后面两个式子只和 \(i,j\) 有关，考虑定义 \[ \begin{aligned} l(i) = \sum_{(u, k) \in E} f(h-1, i, u) \\ r(j) = \sum_{(k, v) \in E} f(h-1, v, j) \end{aligned} \] 这样就能 \(O(n^2)\) 转移了。

现在考虑如何钦定第一步和最后一步的按法。

注意到总限制数只有 \(\mathcal{O}(q)\) 的级别，考虑直接加入 \(q\) 个虚点，编号为 \(n+1\) 到 \(n+q\) 。

钦定当 \(n < i \le n + q\) 时表示起点为 \(s\) 且第一步按了 \(b_s\) （第 \(i-n\) 个询问的 \(s,b_s\)），当 \(j > n\) 时同理。

这样第 \(i~(1\le i \le q)\) 个询问的答案就是 \(f(m, n+i,n+i)\) 。虚点在转移时候判断一下 \(h,k\) 即可。

时间复杂度 \(\mathcal{O}(mn(n+q)^2)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
const int mod = 1e9 + 7;
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
void add(int &x, int y) { (x += y) >= mod ? x -= mod : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N 66

char a[N][N];
int l[N * 2], r[N * 2], dp[N][N * 2][N * 2];
struct query{ int bs, s, bt, t; } qry[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n, m, q; cin >> n >> m >> q;
    rep(i, 1, n) { cin >> (a[i] + 1); rep(j, 1, n) { a[i][j] -= '0'; } }
    rep(i, 1, q) { cin >> qry[i].bs >> qry[i].s >> qry[i].bt >> qry[i].t; }
    rep(h, 1, m)
    {
        int (*now)[N * 2] = dp[h], (*pre)[N * 2] = dp[h - 1];
        rep(i, 1, n + q) rep(j, 1, n + q) now[i][j] = pre[i][j];
        rep(k, 1, n)
        {
            rep(i, 1, n) l[i] = r[i] = (i == k);
            rep(i, 1, q)
            {
                l[n + i] = (qry[i].bs == h && qry[i].s == k);
                r[n + i] = (qry[i].bt == h && qry[i].t == k);
            }
            rep(i, 1, n + q) rep(j, 1, n) { if(a[j][k]) add(l[i], pre[i][j]); }
            rep(i, 1, n) rep(j, 1, n + q) { if(a[k][i]) add(r[j], pre[i][j]); }
            rep(i, 1, n + q) rep(j, 1, n + q) add(now[i][j], l[i] * r[j] % mod);
        }
    }
    rep(i, 1, q) cout << dp[m][n + i][n + i] << '\n';
    return 0;
}