P11802
lsj2009
·
·
题解
Preface
出题人题解。
为啥这个题只过了 3 个人啊？？其实根本不难啊。
Description
有一些环、链、孤立点，你需要将后两者直接相互连边得到若干个环（链与链不能合并在一个环中），使得最终得到的图存在 c 次方根。
求方案总数，向 998244353 取模。
## Solution
### Part 1
我们先考虑然后判断一个图是否存在 $c$ 次方根（这个可能是比较典的？）。
考虑一个图取 $c$ 方后会有啥变化。首先对于每个环我们可以分开了考虑；考察一个环，有经典结论：
- 一个长度 $len$ 的环会分裂成 $\gcd(c,len)$ 个长为 $\frac{len}{\gcd(c,len)}$ 的环。
> **Proof：**
>
> 对环重标号，考虑从节点 $x$ 在新图上向后走 $k$ 步又回到了 $x$，则有 $x+kc\equiv x\pmod{len}$。
>
> 解得 $k_{\min}=\frac{len}{\gcd(c,len)}$，则我们就得到了上面的结论。
即 **原图上的一个环会在新图上变成若干个长度相同的环**；那么我们倒过来考虑，则我们需要把新图上的若干个长度相同的环给合并回去。
具体的，考虑当前环长为 $len$，根据上面结论，$p$ 个长度为 $len$ 的环合并的充要条件是 $\gcd(c,p\cdot len)=p$。
我们找出所有满足条件的 $p$，若他们可以拼凑出 $cnt_{len}$（一个 $p$ 可以多次是用），那么就是合法的。
实现上我们跑一个可行性完全背包即可。
但是我们可以做到更优：有结论是：
- 我们找到最小的满足条件的 $p$，则可以拼凑出 $m$ 满足条件 **当且仅当 $m$ 是 $p$ 的倍数**。
> **Proof：**
>
> 记 $t=p_{\min}$。
>
> 观察条件：$\gcd(c,p\cdot len)=p\Rightarrow c\equiv 0\pmod{p}\wedge \gcd(\frac{c}{p},len)=1$。
>
> 写出 $p,len,c$ 的唯一分解形式：
> - $p=\prod q_i^{\alpha_i}$。
> - $len=\prod q_i^{\beta_i}$。
> - $c=\prod q_i^{\gamma_i}$。
>
> 则上面条件等价于：对于任意的 $i$ 有 $\min(\gamma_i-\alpha_i,\beta_i)=0$。
>
> 如果 $\beta_i=0$，我只需要有 $0\le \alpha_i\le \gamma_i$；否则我们要有 $\alpha_i=\gamma_i$。
>
> 考虑 $t$ 关于 $q_i$ 的指数 $\delta_i$，显然为前者情况时必有 $\delta_i=0$，否则 $\delta_i=\gamma_i$。
>
> 则我们可以得到，对于任意 $i$ 有 $\alpha_i\ge \delta_i$，也就是 $p$ 必然是 $t$ 的倍数（并且由于 $t$ 是 $p$ 的 $\min$，所以存在一个 $p$ 可以取等）。
>
> 那么接下来根据平凡的分析，我们就可以得到上面的结论。
### Part 2
接下来我们来考虑计数问题。
下面记 $m$ 为孤立点个数，$a_i$ 为长为 $i$ 的链的个数，$b_i$ 为长为 $i$ 的环的个数，$t_i$ 为上面提到的当 $len=i$ 时的 $p_{\min}$。
计数的一个比较困难的点是我两条长度分别为 $2,3$ 的环补全为 $3,4$ 和补全为 $4,3$ 是不同的，也就是我每次考虑最终补全的一个大小为 $x$ 的环，如果从这个角度再进行计数的话，需要考虑的是前面选的环是有影响的。
那么我们这样子考虑：记录状态 $f_{i,j,k}$ 表示的是我当前考虑到了所有 $len\le i$ 的最终环的情况，然后还有 $j$ 个孤立点没有使用，还有 $k$ 条链没有封闭成环的方案总数。
考虑我们对于每个链到环的补全不是我在环的角度去选择一个链变成他，而是 **我每次往我现在还没有确定长度的链（也就是长度要 $>i$）的后面塞一个节点**。
而我们在最开始将 dp 数组初始化为 $m!$，这样子所有的孤立点也就变得 **不同**，即对应我们接下来 **依次取第一个孤立点塞到最后面**。
即我们要保证说我当前没有封闭成环的 $k$ 条链长度均为 $i$。
给出转移方程：
$$
\frac{f_{i-1,j,k}}{k!}\cdot(k+a_i)!\to f_{i,j+k,k+a_i}
$$
对于其中系数的解释是：我们认为这 $k$ 条链的是 **不同的**（其实和上面孤立点的处理是一样的），这一点是因为我们每次将不同的链封闭成环的方案数是不同的，这样子我们将链封闭成环只需要取一个前缀。
然后等把这些链都封闭成长为 $i'$ 的环的时候，再除掉前缀的长度的阶乘消除这些环又是相同的影响即可。
那么接下来我们也就要考虑把组成环的转移。
我们考虑枚举：我们用 $is$ 个孤立点组成了只有孤立点构成的 $s$ 个环，又拿出了前 $p$ 个环把他们封闭成环，则我们有：
$$
\frac{f_{i,j,k}}{i^ss!p!}[(s+p+b_i)\equiv 0 \pmod{t_i}]\to f_{i,j+is,k-p}
$$
对于系数的解释大概是：
- 这里的 $p!$ 就是上面提到的，这取出的 $p$ 条链封闭成环后又是 **相同** 的。
- $s!$ 与 $p!$ 同理。
- $i^s$ 是因为我们注意到这 $s$ 个环实际上都是个 **圆**，注意到圆排列方案数，我们要除掉一个 $\frac{(i-1)!}{i}=\frac{1}{i}$ 的系数。
分析上面那个算法的复杂度：注意到我们有 $p,s,k\le \lfloor\frac{n}{i}\rfloor$，所以复杂度即为：
$$
\mathcal{O}\left(\sum\limits_{i=1}^n \left (\frac{n}{i}\right )^3n\right)=\mathcal{O}\left(n^4\int_{1}^n \left (\frac{1}{x}\right )^3\mathrm{d}x\right)=\mathcal{O}(n^4)
$$
这个算法常数非常小并且跑不满（如果实现优秀的话），出题人尝试卡掉这个做法，不知道有没有成功（
### Part 3
考虑进一步优化：我们注意到其实最上面那个转移复杂度已经是 $\mathcal{O}(n^3)$，可以接受，考虑优化后面那步转移。
观察到其实对于 $p$ 和 $s$，除了 $[(s+p+b_i)\equiv 0 \pmod{t_i}]$ 这个系数之外，其系数和影响的维度都是互相独立的，我们可以对其进行分步卷积，注意到是 $\mathcal{O}(n^3)$ 的。
而如果其实考虑到这个系数关系也不大，我们将 $p$ 和 $s$ 按模 $t_i$ 进行划分等价类，我们每次取出对于 $p$ 的余 $r$ 和对于 $s$ 的余 $-r-b_i$ 的两个类，进行卷积即可。
由于每个 $p$ 和 $s$ 都还是之后进行一次卷积，所以复杂度仍然是 $\mathcal{O}(n^3)$ 的。
常数很小，可以通过所有测试点。
## Code
```cpp
#include<bits/stdc++.h>
//#define int long long
//#pragma GCC optimize(3,"Ofast","inline")
#define ll long long
#define i128 __int128
#define ull unsigned long long
#define ld long double
#define PII pair<int,int>
#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3f
#define chkmax(a,b) a=max(a,b)
#define chkmin(a,b) a=min(a,b)
#define rep(k,l,r) for(int k=l;k<=r;++k)
#define per(k,r,l) for(int k=r;k>=l;--k)
#define cl(f,x) memset(f,x,sizeof(f))
using namespace std;
void file_IO() {
freopen("count.in","r",stdin);
freopen("count.out","w",stdout);
}
bool M1;
template<int p>
struct mint {
int x;
mint() {
x=0;
}
mint(int _x) {
x=_x;
}
friend mint operator + (mint a,mint b) {
return a.x+b.x>=p? a.x+b.x-p:a.x+b.x;
}
friend mint operator - (mint a,mint b) {
return a.x<b.x? a.x-b.x+p:a.x-b.x;
}
friend mint operator * (mint a,mint b) {
return 1ll*a.x*b.x%p;
}
friend mint operator ^ (mint a,ll b) {
mint res=1,base=a;
while(b) {
if(b&1)
res*=base;
base*=base; b>>=1;
}
return res;
}
friend mint operator ~ (mint a) {
return a^(p-2);
}
friend mint operator / (mint a,mint b) {
return a*(~b);
}
friend mint & operator += (mint& a,mint b) {
return a=a+b;
}
friend mint & operator -= (mint& a,mint b) {
return a=a-b;
}
friend mint & operator *= (mint& a,mint b) {
return a=a*b;
}
friend mint & operator /= (mint& a,mint b) {
return a=a/b;
}
friend mint operator ++ (mint& a) {
return a+=1;
}
friend mint operator -- (mint& a) {
return a-=1;
}
};
const int MOD=998244353;
#define mint mint<MOD>
const int N=3e3+5;
int p[N],n,k,cnt1[N],cnt2[N],in[N],g[N],c;
bool used[N];
mint f[2][N][N],jc[N],inv_jc[N],inv_p[N][N],h[N][N],tmp[N][N];
vector<int> vecs[N],vecp[N];
void init(int n=3e3) {
jc[0]=1;
rep(i,1,n)
jc[i]=jc[i-1]*i;
inv_jc[n]=~jc[n];
per(i,n-1,0)
inv_jc[i]=inv_jc[i+1]*(i+1);
}
mint C(int n,int m) {
if(n<m)
return 0;
return jc[n]*inv_jc[n-m]*inv_jc[m];
}
void dfs(int x,int len) {
if(x==-1) {
++cnt1[len];
return;
}
if(used[x]) {
++cnt2[len];
return;
}
++c;
used[x]=true;
dfs(p[x],len+1);
}
void solve() {
scanf("%d%d",&n,&k);
rep(i,1,n) {
int d=__gcd(i,k);
if(!g[i/d])
g[i/d]=d;
}
rep(i,1,n) {
scanf("%d",&p[i]);
if(p[i]!=-1)
++in[p[i]];
}
rep(i,1,n) {
if(p[i]!=-1&&!in[i])
dfs(i,0);
}
rep(i,1,n) {
if(p[i]!=-1&&!used[i])
dfs(i,0);
}
c=n-c;
int tot=0;
rep(i,0,c)
f[1][i][0]=jc[c]*inv_jc[i];
rep(i,2,n) {
int m=n/i,d=g[i];
tot+=cnt1[i];
rep(j,0,m)
inv_p[i][j]=~(mint(i)^j);
rep(j,0,c) {
rep(k,0,tot)
f[i&1][j][k]=h[j][k]=0;
}
rep(j,0,c) {
rep(k,0,min(tot-cnt1[i],c-j))
h[j+k][k+cnt1[i]]+=f[(i-1)&1][j][k]*inv_jc[k]*jc[k+cnt1[i]];
}
if(!d) {
if(cnt2[i]) {
puts("0");
return;
}
rep(j,0,c) {
rep(k,0,tot)
f[i&1][j][k]=h[j][k];
}
continue;
}
rep(i,0,d-1) {
vecp[i].clear();
vecs[i].clear();
}
rep(p,0,min(tot,n/i))
vecp[p%d].push_back(p);
rep(s,0,c/i)
vecs[s%d].push_back(s);
rep(pm,0,d-1) {
vector<int> vp=vecp[pm],vs=vecs[((d-pm-cnt2[i])%d+d)%d];
if(vp.empty()||vs.empty())
continue;
rep(j,0,c) {
rep(k,0,tot)
tmp[j][k]=0;
}
for(auto p:vp) {
rep(j,0,c) {
rep(k,p,min(tot,n/i))
tmp[j][k-p]+=h[j][k]*inv_jc[p];
}
}
for(auto s:vs) {
rep(j,0,c-i*s) {
rep(k,0,min(tot,n/i))
f[i&1][j+i*s][k]+=tmp[j][k]*inv_jc[s]*inv_p[i][s];
}
}
}
}
printf("%d\n",f[n&1][c][0].x);
}
bool M2;
// g++ T6.cpp -std=c++14 -Wall -O2 -o T6
signed main() {
// file_IO();
int testcase=1;
init();
//scanf("%d",&testcase);
while(testcase--)
solve();
cerr<<"used time = "<<1000*clock()/CLOCKS_PER_SEC<<"ms\n";
cerr<<"used memory = "<<(&M2-&M1)/1024/1024<<"MB\n";
return 0;
}
```