【题解】ABC319G Counting Shortest Paths

· · 题解

更好的阅读体验

G.Counting Shortest Paths

题目分析：

注意到我们只需要在所有的边都被删完了，再进行询问。

所以可以考虑直接从小到大枚举最短路长度，也就是从 1 开始一步步扩展直到扩展到 n。

所以一个直观的想法就是一步步预处理出 f[i][j] 表示 1 到 i 路径长度为 j 的方案数，O(n) 转移显然。

考虑优化，f[i][j] 的第二维显然只有当 j 为 1 到 i 的最短路时才有意义，所以可以将其它的所有忽略，总状态数变成了 O(n)。

对于转移，因为是现在的点对其余所有的点产生贡献，所以可以直接一起转移，只有 O(m) 次转移才是需要特殊注意的，所以只需要管这 O(m) 次转移，转移的总复杂度为 O(m)。

设 n,m 同阶，则总时间复杂度为 O(n)。

代码中为了好写，使用了 set 复杂度会变成 O(n \log n)，以及有一个细节是我们如果直接将 f 对 998244353 取模那么就无法判断是否能转移到对应的节点，所以要特别记录一下。

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5+5;
const int MOD = 998244353;
set<int> E[N],cur,lst,tmp;
int cnt[N],a[N],tot[N];
signed main(){
    int n,m;scanf("%lld%lld",&n,&m);
    for(int i=1; i<=m; i++){
        int u,v;scanf("%lld%lld",&u,&v);
        E[u].insert(v);
        E[v].insert(u);
    }
    cnt[n] = 1;
    cur.insert(n);
    for(int i=1; i<n; i++)  lst.insert(i);
    while(!cur.empty()){
        int res = 0,res2 = 0;
        for(auto now : cur) res = (res + cnt[now])%MOD,res2++;
        for(auto to : lst)  cnt[to] = (cnt[to] + res)%MOD,tot[to] = 0;
        for(auto now : cur){
            for(auto to : E[now]){
                if(lst.find(to) != lst.end())  //避免奇奇怪怪的相互影响 
                    cnt[to] = (cnt[to] - cnt[now] + MOD)%MOD,tot[to]++;
            }
        }
        for(auto now : cur){
            int tot = 0;
            for(auto to : E[now])   a[++tot] = to;
            for(int i=1; i<=tot; i++){
                E[a[i]].erase(now);
                E[now].erase(a[i]);
            }
        }
        swap(tmp,lst);
        cur.clear(),lst.clear();
        for(auto i : tmp){
            if(tot[i] != res2){  //tot 其实就是记录一下是不是有点可以转移到他 
                cur.insert(i);
                if(i == 1){
                    printf("%lld\n",cnt[1]);
                    return 0;
                }
            }
            else    lst.insert(i);
        }
        tmp.clear();
    }
    printf("-1\n");
    return 0;
}