UOJ279 【UTR #2】题目交流通道题解

题意：

定好了难度，雄心勃勃的 cxy 开始寻找智慧的神犇星球的居民出题。

然而 cxy 没有料到，神犇星球的居民告诉 cxy ：“今年神犇星球经济不景气，大家都想宅在家里，哪有心思出来出题呢？”

为了挽救这一局面， cxy 决定为神犇星球建一些高速传送通道促进该星球各地区之间交流题目。

神犇星球有 \(n\) 座小城。对于任意两座小城 \(v, u\)（\(v \neq u\)）， cxy 想在 \(v, u\) 之间建立一个传送时间为 \(w(v, u)\) 的无向传送通道，其中 \(w(v, u)\) 为不超过 \(k\) 的非负整数。建成后，神犇星球的居民可从一座小城出发经过一个或若干个传送通道到达另一座小城交流题目，花费的时间为所有经过的传送通道的传送时间之和。

cxy 还没有决定每一个传送通道的传送时间取值，只是对于任意两座小城 \(v, u\)，决定了从 \(v\) 出发到达 \(u\) 的最短时间要恰好等于 \(d(v, u)\)。但 cxy 日理万机，于是他找到了你 —— IOI AKer，请你帮助 cxy 数一数有多少种不同的满足条件的传送通道建设方案吧！

由于方案数可能很大，你只用输出方案数对 \(998244353\)（\(7 \times 17 \times 2^{23}+1\)，一个质数）取模后的结果。

输入格式：

第一行两个整数 \(n, k\)。保证 \(n \ge 1, k \ge 0\)。

接下来 \(n\) 行，每行有 \(n\) 个非负整数，第 \(i\) 行的第 \(j\) 个数表示 \(d(i,j)\) 的值。

输出格式：

输出一行，一个整数，表示方案数对 \(998244353\) 取模的结果。如果无解，则方案数为 \(0\)。

数据范围：

\(1 \le n \le 400, ~0\le k \le 10^9,~0\leq d(u,v)\leq 10^{9}\)

计数型 dp + Floyd 好题。

首先如果下面三个条件不满足，那么一定是无解的 \[ d(i,i)=0,~d(i,j)=d(j,i),~d(i,j) \le d(i,k) + d(k,j) \] 接着考虑 \(d(i,j) \ge 1 (i\ne j)\) 的情况。

根据 \(\mathrm{Floyd}\) 算法的性质可知

如果存在点 \(k\) 使得 \(d(i,j) = d(i,k) + d(k,j)\) ，则只需要满足 \(w(i,j) \ge d(i,j)\) 即可
否则，一定有 \(d(i,j) = w(i,j)\) 。

因此对于这样的情况，直接跑 \(\mathrm{Floyd}\) 算答案即可。具体计算方法见下文。

然后考虑 \(d(i,j) \ge 0\) 的情况。

为什么要单独考虑这种情况呢？

因为此时「存在 \(k\) 使得 \(d(i,j) = d(i,k) + d(k,j)\) 」并不能保证 \(w(i,j)\) 可以大于 \(d(i,j)\) 。

举个例子，当 \(d(i,k)=0\) 时，显然有 \(d(i,j) = d(k,j)\) 。

但如果所有的 \(k\) 都有 \(w(k,j) > d(k,j)=d(i,j)\) ，此时 \(w(i,j)\) 就不能取除 \(d(i,j)\) 以外的任何值。

那么怎么办呢？仔细思考可以发现，这些满足 \(d(i,k)=0\) 的 \(k\) 一定与 \(i\) 处在一个「两两距离为 \(0\) 的连通块」内。

因此我们可以考虑缩点。不妨假设缩点后，\(i\) 在新点 \(I\) 中， \(j\) 在新点 \(J\) 中。则此时一定有 \(d(I,J) \ge 0\) 。

现在我们来考虑如何计算缩点后 \(w(I,J)\) 的贡献。

首先如果存在 \(K\) 使得 \(d(I,J) = d(I,K) + d(K,J)\) ，则只要满足 \(w(I,J) \ge d(I,J)\) 即可 \[ [w_{\max} - d(I,J)+1]^{\mathrm{size}(I)\times \mathrm{size}(J)} \] 否则，还要满足至少要有一条边 \(w(I,J)=d(I,J)\) ，根据容斥可知（也就是去掉全大于的情况） \[ [w_{\max} - d(I,J)+1]^{\mathrm{size}(I)\times \mathrm{size}(J)} - [w_{\max} - d(I,J)]^{\mathrm{size}(I)\times \mathrm{size}(J)} \]

最后考虑「两两距离为 \(0\) 的连通块」内部的贡献。

~~据说这是一个经典的容斥，反正我之前没碰到过~~。

设 \(F_n\) 表示 \(n\) 个点的「两两距离为 \(0\) 的连通块」的不同方案数。

设 \(G_n\) 表示 \(i\) 个点仅考虑 \(w_{\max}\) 时所有合法图的方案数，即 \(G_n = (w_{\max} + 1)^{\binom{n}{2}}\)

根据容斥， \(F_n\) 就等于 \(G_n\) 减去所有不符合条件的方案数。

枚举 \(1\) 号点所在的「两两距离为 \(0\) 的连通块」的大小 \(i\) ，则 \[ F_n = G_n - \sum_{i=1}^{n-1}\dbinom{n-1}{i-1}F_{i}G_{n-i}\times w_{\max}^{i(n-i)} \] 这里枚举 \(1\) 号点是因为不枚举会重复计数，重复类似于洛谷P4547 [THUWC2017]随机二分图。

然后解释一下后面那个东西是啥含义。

\(\binom{n-1}{i-1}F_{i}G_{n-i}\) 这个是因为枚举的块内部要保证合法，其他点随便怎么搞都行。
\(w_{\max}^{i(n-i)}\) 这个是因为两个团之间不能有 \(0\) 边，即连接的 \(i \times (n-i)\) 条边只能选 \(1\sim w_{\max}\) 。

那么最后只要对每个连通块 \(I\) （即缩点后的新点），令 \(\mathtt{ans} \gets \mathtt{ans} \times F_{\mathrm{size}(I)}\) 即可。

时间复杂度 \(O(n^3)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(455))
const int mod = 998244353;
void add(int &x,int y) { x = (x + (y % mod) + mod) % mod; }

int n,mx,V,ans=1,top[N],fa[N],sz[N],fac[N],invf[N],d[N][N],c[N][N],F[N],G[N];
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
int mul(int cnt, ...)
{
    va_list ptr; va_start(ptr, cnt); int res=1;
    for(int i=0; i<cnt; i++) res = res * va_arg(ptr,int) % mod;
    va_end(ptr); return res;
}
bool test(int x,int y, bool un=0)
{
    if((x = find(x)) == (y = find(y))) return 1;
    if(un) sz[x] > sz[y] ? swap(x,y) : (void)0, fa[x] = y, sz[y] += sz[x];
    return 0;
}
int qpow(int a,int b,int c=1)
{ for(a %=mod; b; b>>=1, a = a * a % mod) if(b&1) c = c * a % mod; return c; }
int C(int n,int k){ return n < k ? 0 : mul(3, fac[n], invf[k], invf[n-k]); }
void init(int n) { for(int i=1; i<=n; i++) fa[i] = i, sz[i] = 1; }
bool init_graph()
{
    for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) cin >> d[i][j];

    for(int i=1; i<=n; i++) if(d[i][i] != 0) return 0;
    for(int i=1; i<=n; i++) for(int j=i; j<=n; j++)
        if(max(d[i][j], d[j][i]) > mx || d[i][j] != d[j][i]) return 0;

    for(int k=1; k<=n; k++) for(int i=1; i<=n; i++) for(int j=1; j<=n; j++)
        if(d[i][j] > d[i][k] + d[k][j]) return 0;
        else c[i][j] += (d[i][j] == d[i][k] + d[k][j]);
    // for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) cout << c[i][j] << " \n"[j==n];
    return 1;
}
void init_dp()
{
    fac[0] = fac[1] = 1; 
    for(int i=2; i<=n; i++) fac[i] = fac[i-1] * i % mod;
    invf[n] = qpow(fac[n], mod-2);
    for(int i=n; i; i--) invf[i-1] = invf[i] * i % mod;
    for(int i=1; i<=n; i++) G[i] = qpow(mx+1, i * (i-1) / 2);
    for(int i=1; i<=n; i++)
    {
        int cur=0; F[i] = G[i];
        for(int j=1; j<i; j++)
            add(cur, mul(4, qpow(mx, j*(i-j)), C(i-1, j-1), F[j], G[i-j]));
        add(F[i], mod-cur);
    }
    // for(int i=1; i<=n; i++) cout << F[i] << " \n"[i==n];
    // for(int i=1; i<=n; i++) cout << G[i] << " \n"[i==n];
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> mx; init(n);
    if(!init_graph()) return cout << "0\n", 0;
    for(int i=1; i<=n; i++) for(int j=i+1; j<=n; j++)
        if(!d[i][j]) test(i,j,1);
    init_dp();
    for(int i=1; i<=n; i++)
        if(fa[i] == i) top[++V] = i, ans = ans * F[sz[i]] % mod;
    // for(int i=1; i<=V; i++) cout << top[i] << " \n"[i==V];
    for(int i=1,u,v,cur; i<V; i++) for(int j=i+1; j<=V; j++)
    {
        u = top[i], v = top[j];
        cur = qpow(mx - d[u][v] + 1, sz[u] * sz[v]);
        if(c[u][v] <= sz[u] + sz[v]) add(cur, -qpow(mx-d[u][v], sz[u] * sz[v]));
        ans = ans * cur % mod;
    }
    cout << (ans + mod) % mod << '\n';
    return 0;
}