[ABC387G] Prime Circuit

发表于 更新于 分类于 ， 阅读次数：
省流：不会正解，直接 unintended sol 爆草！

Statements

给定 \(n\)，求满足下列条件的 \(n\) 点有标号、连通、简单、无向图的数量：

对于该图中任意不重复经过某条边的环，其长度都为质数。

Data range：\(n\le2.5\times10^5\)。

Time limit：12s。

Solution

首先肯定要刻画一下这图长啥样。

考虑一个边双的形状。

Lemma：一个边双必然是一个环或一个单点。

Proof：如果不是，那么至少有两个环。

考虑随便拿出两个相交于一条链的环（链可能退化成点）。那么这条链有两个端点 \(x,y\)。

画个图就能得知，此时 \(x,y\) 之间存在三条互不相交的路径，设其长度为 \(a,b,c\)。（如果 \(x=y\)，那么有一个是 \(0\)。）

此时容易至少发现存在三个长分为 \(a+b,b+c,c+a\) 的环。

显然环长不可能为 \(2\)，所以环长为奇（质）数，所以其和也是奇数。但又有环长之和等于 \((a+b)+(b+c)+(c+a)=2(a+b+c)\) 是偶数，矛盾！

考虑钦定所有环长为 \(l_1,l_2,\ldots,l_k\)，然后计数：

  • 每个环有 \(\dfrac{(l_i-1)!}{2-[l_i=1]}\) 种方案；
  • 将这些环连成一棵树（因为边双缩起来是树），根据这里的结论可以得到方案数为 \(n^{k-2}\cdot\prod l_i\)；
  • 分配环中的点，这个就是一堆组合数。

然后就可以考虑 dp。

令 \(dp_i\) 表示还剩 \(i\) 个点时，方案数乘 \(n^2\)（这样那个幂就变成了 \(n^k\)）的值。

那么不难列出转移方程：

\[dp_i=\sum_{\substack{(j\in\mathbb P\land j\ne2)\lor j=1\\i+j\le n}}\binom{i+j-1}{j-1}\cdot\frac{(j-1)!}{2-[j=1]}\cdot j\cdot n\cdot dp_{i+j}\]

其中组合数是分配点；\(n\) 是对 \(n^k\) 的贡献。初值为 \(dp_n=1\)；答案即为 \(\dfrac{dp_0}{n^2}\)。

由结论可知 \(|\mathbb P|=\Theta\left(\dfrac n{\log n}\right)\)；所以总复杂度为 \(\Theta\left(\dfrac{n^2}{\log n}\right)\)。

这玩意写的时候注意一下常数就可以通过了。

  • 什么？你说 \(o(n^{1.99})\) 做法？我太菜，不会。

Code

在 AT 机子上跑了 10.66s，还是需要一点卡常。

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
// Author: YE Minghan
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define PB emplace_back
#define PPB pop_back
#define MP make_pair
#define ALL(Name) Name.begin(),Name.end()
#define PII pair<int,int>
#define VI vector<int>
#define GI greater<int>
#define fi first
#define se second

const int MOD=998244353,N=250005;
int n;
int fac[N],ifac[N];
int dp[N];
int pw(int x,int y=MOD-2)
{
	int r=1;
	while(y)
	{
		if(y&1)r=1ll*r*x%MOD;
		x=1ll*x*x%MOD,y>>=1;
	}
	return r;
}
bool p[N];
VI S;

int main()
{
	ios::sync_with_stdio(false),cin.tie(nullptr);
//	int _;cin>>_;while(_--)

	cin>>n;
	fac[0]=1;
	for(int i=1;i<=n;i++)fac[i]=1ll*fac[i-1]*i%MOD,p[i]=1;
	ifac[n]=pw(fac[n]);
	for(int i=n-1;~i;i--)ifac[i]=(i+1ll)*ifac[i+1]%MOD;
	for(int i=2;i<=n;i++)
		if(p[i])
			for(int j=i<<1;j<=n;j+=i)p[j]=0;
	S.PB(1);
	for(int i=3;i<=n;i++)
		if(p[i])S.PB(i);
	dp[n]=1;
	for(int i=n-1;~i;i--)
	{
		for(int j:S)
		{
			if(i+j>n)break;
			dp[i]=(dp[i]+(1ll+(j==1))*fac[i+j-1]*j%MOD*dp[i+j])%MOD;
		}
		dp[i]=1ll*dp[i]*n%MOD*ifac[i]%MOD*(MOD+1>>1)%MOD;
	}
	cout<<1ll*dp[0]*pw(n,MOD-3)%MOD<<endl;

	return 0;
}