不是，这个能在 ACM 场上被这么多队切？
题目链接。
题意
对于一张
个点的无向图，称它是好的，当且仅当对于每一对 ，都存在路径 使得 。
称一张图是完美的，当且仅当它是好的，并且是所有 个点的好的图中，边数最小的。
给定 ，求完美的图的数量。
。
题解
考虑什么样的图是好的。
可以发现，一个图是好的当且仅当，对于每一个 ，所有 的倍数点的导出子图连通。
证明：
必要性：考虑找到最大的
使得导出子图不连通，则存在 与
不连通且 。
充分性：设 ，则在
倍数导出子图上先从 走到 再走到 即可。
再来考虑什么样的图是完美的。
假如这张图里有若干条边，对于每一条边 ，我们假设按照 从大到小顺序加边。
现在考虑，
的边已经加完了，会加入哪些 的边。
令 ，现在考虑点 导出子图内的边。
对于一个质数 ，可以发现
，则 与 连通。
对于一个质数 ，显然
没有和其他点连边。
对于一个合数 ，可以发现 一定与其他某个点连通。
令
中质数的个数，那么这个导出子图由一个 的连通块和 个孤立点组成。
那么如果要让这个导出子图连通，至少需要连 条边。
而要让边的个数最少，一定是恰好只会连 条边，连边的方案数可以使用 prufer
序列算出来。
设
表示此时的方案数，则答案为 ，可以使用数论分块计算。
发现我们还需要求出某个区间内的质数个数，这可以用 Min_25 筛中求 的部分算出。
最终复杂度为 ，瓶颈在 Min_25 筛。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
| #include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3fll
#define debug(x) cerr<<#x<<"="<<x<<endl
using namespace std;
using ll=long long;
using ld=long double;
using pli=pair<ll,int>;
using pi=pair<int,int>;
template<typename A>
using vc=vector<A>;
inline int read()
{
int s=0,w=1;char ch;
while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
inline ll lread()
{
ll s=0,w=1;char ch;
while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
const int mod=998244353;
int pri[400005];
bool is[400005];
ll g[2][400005];
ll f1[400005];
ll f2[400005];
ll sq,n;
inline ll qow(ll a,ll b)
{
ll ans=1;
while(b)
{
if(b&1) ans=ans*a%mod;
a=a*a%mod;
b>>=1;
}
return ans;
}
inline ll& gp(ll w)
{
if(!w) return g[0][0];
if(w<=sq) return g[0][w];
return g[1][n/w];
}
inline ll get(ll m)
{
ll v=gp(m)-gp(m/2)+1;
if(m==1) return 1;
if(v==m) return qow(m%mod,m-2);
return (m-v)%mod*qow(m%mod,v-1)%mod;
}
int main()
{
n=lread();
for(;(sq+1)*(sq+1)<=n;sq++);
for(int i=2;i<=sq;i++)
{
if(!is[i]) pri[++pri[0]]=i;
for(int j=1;j<=pri[0]&&i*pri[j]<=sq;j++)
{
is[i*pri[j]]=1;
if(i%pri[j]==0) break;
}
}
vc<ll>num;
for(ll i=1;i<=sq;i++) num.push_back(i);
for(ll i=sq;i;i--) num.push_back(n/i);
num.erase(unique(num.begin(),num.end()),num.end());
for(ll i:num) gp(i)=i-1;
unsigned sw=0;
for(int i=1;i<=pri[0];i++)
{
while(sw<num.size()&&(ll)pri[i]*pri[i]>num[sw]) sw++;
for(unsigned j=num.size()-1;j>=sw;j--) gp(num[j])-=gp(num[j]/pri[i])-(i-1);
}
ll ans=1;
for(ll l=1,r;l<=n;l=r+1)
{
r=n/(n/l);
ans=ans*qow(get(n/l),r-l+1)%mod;
}
printf("%lld\n",ans);
return 0;
}
|