看数据范围
——题记
考虑记
\(f_i\) 表示有 \(i\) 个点的完全图的圈数
\(g_i\) 表示有 \(i\) 个点的完全图中一个点到另一个点不同路径的方案数
\(ans\) 表示答案
容易知道递推式
\[f_i=g_{i-1} \times C_{i-1}^2+f_{i-1}
\]
\[g_i=g_{i-1} \times (i-2) + 1
\]
\[ans=f_{n-1}+g_{n-1}\times C_{n-2}^2
\]
因为 \(f_i\) 和 \(g_i\) 只跟 \(f_{i-1}\) 和 \(g_{i-1}\) 有关，所以使用滚动数组
然后看数据范围
\[9.99\times 10^8\le n\le 10^9
\]
我们发现，哪怕是最后一个数据范围，假如知道了 \(f_{9.99\times 10^8}\) 和 \(g_{9.99\times 10^8}\)，最多只用计算 \(10^6\) 就可以算出答案（原来是这样解决的吗？太神奇了。我想了一小时才想出来）
预处理就好，不用多久（用上面那个递推式计算，等一分钟就好了）
上代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod=998244353;
ll T,n,f,g;
ll t1=876466444,t2=141309211;
int main()
{
scanf("%lld",&T);
while(T--)
{
scanf("%lld",&n);
if(n==3)
{
puts("0");
continue;
}
if(n<=1000000)
{
f=1,g=2;
for(ll i=4;i<n;i++) //注意这里假如是 int 的话会爆 int，因为下面有 (i-1)*(i-2)
f=(f+g*(((i-1)*(i-2)/2)%mod)%mod)%mod,g=(g*(i-2)%mod+1)%mod;
printf("%lld\n",(f+g*(((n-2)*(n-3)/2)%mod)%mod)%mod);//同理 n 也要 long long
}
else
{
f=t1,g=t2;
for(ll i=998999999;i<n;i++)
f=(f+g*(((i-1)*(i-2)/2)%mod)%mod)%mod,g=(g*(i-2)%mod+1)%mod;
printf("%lld\n",(f+g*(((n-2)*(n-3)/2)%mod)%mod)%mod);
}
}
return 0;
}