[ABC319G]题解

markding · 2023-09-10 15:00:02 · 题解

提供一种奇奇怪怪的思路。

设 f_{i,j} 表示从点 1 走 i 步到点 j 的方案数。

初值为 f_{0,1}=1,\ f_{0,i}=0\ (2\le i\le n)。

转移式为 f_{i,j}=\sum_{(j,k)\in E} f_{i-1,k}。

而此题要求的答案则为 f_{t,n}，其中 t 是最小的一个数满足 f_{t,n}>0。若这样的 t 不存在，输出 -1。

对于 f 数组从 f_{i-1,j} 向 f_{i,j} 的转移，有 O(N+M) 的方法。

首先我们算出 \sum^n_{j=1}f_{i-1,j} 的值，记为 sum，则 f_{i,j}=sum-\sum_{(j,k)\notin E}f_{i-1,k}。

由于这是一个删去了 M 条边的无向完全图，故 \sum_{1\le j,k\le n}[(j,k)\notin E] 的值是 N+2M。我们只需求和后做 N+2M 次减法就行了。

注意到题目中的最短路不会很长（？），所以我们直接套用上述做法 666 次即可。

如果在第 t 次迭代后 f_{t,n}>0，那么答案就是 f_{t,n}。

如果 666 次迭代后 f_{666,n} 的值依旧为 0，那么直接输出 -1 即可（？）。

本人的实现复杂度为 O(round(n+m))\approx4\times10^8（代码中 round 的值为 666），时间较满。

UPD 于 2024/5/3: 被 after_contest 制裁力（大悲），hack 数据的答案是 998244353 的倍数，取模后等于 0，会被当做无解输出。

解决方法很简单，我们只需将代码中的运算对 998244353d（d 为正整数）取模，最后对于 998244353 取模后输出即可。

当 d 越大时，数据便越难构造（？），我们卡过去的概率越大，代码中 d=7。

#include<iostream>
#define int long long
#define mod 998244353
#define Mod 6987710471
#define N 200005
using namespace std;
int n,m,u[N],v[N],f[N],g[N];
signed main()
{
    cin>>n>>m,f[1]=1;
    for(int i=1;i<=m;i++)cin>>u[i]>>v[i];
    for(int rd=1;rd<=666;rd++)
    {
        int sum=0;
        for(int i=1;i<=n;i++)sum=(sum+f[i])%Mod;
        for(int i=1;i<=n;i++)g[i]=(sum-f[i]+Mod)%Mod;
        for(int i=1;i<=m;i++)
            g[u[i]]=(g[u[i]]-f[v[i]]+Mod)%Mod,
            g[v[i]]=(g[v[i]]-f[u[i]]+Mod)%Mod;
        for(int i=1;i<=n;i++)f[i]=g[i];
        if(f[n]){cout<<f[n]%mod;return 0;}
    }
    cout<<-1;
}