洛谷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;
}