【JZOJ100207】【20190705】决心

题目

你需要构造一个排列

初始时$p_i=i$，一次操作定义为：

选择一些$(x_i,y_i)$，满足每个数字只能出现一次
依次交换$p_{x_i},p_{y_i}$

定义一个排列 $P$ 的最少交换次数为$f(P)$

现在 $P$ 有 $k$ 个位置的排列顺序是未知的，定义某一种确定顺序的方案是$P'$

求$\sum f(P')$

$1 \le n \le 10^6 \ , \ k \le min(12,n)$

题解

首先操作次数不会超过2，考虑每一个轮换
考虑一个排列$P$，它的贡献是：

1.如果所有轮换的大小<=2 ，最少的步数为0/1，贡献为0

2.如果存在轮换的大小>2，最少的步数为2，考虑贡献

大小不同的轮换不会互相影响

大小相同的轮换可以两两拼在一起，也可以单独存在

写成dp即$h_{i,j} \ = \ h_{i,j-1}i + h_{i,j-2}(j-1)i $

如果大小为$i$的轮换有$m_i$个，总贡献为$\prod h_{i,m_i}$
如果确定的点指向不确定的点存在一条链$l$，那么就把不确定的点的大小看做$|l|+1$
预处理出所有的$h$，这样就可以只考虑不确定的点的排列
由于贡献只和轮换的大小有关，可以枚举集合划分再把贡献乘以一个圆排列
时间复杂度$O(n \ log \ n + bell(k) \ k)$

Code

#include<bits/stdc++.h>

#define pb push_back

using namespace std;

const int N=1000010,mod=1e9+7;

int n,k,p[N],q[N],cnt[N],pos[N],a[N],b[N],c[N],bl[N],iv[N],vis[N],T,preans,precnt[N],ans,fac[N],prefg1,prefg2,Bell;

vector<int>h[N];

void inc(int&x,int y){x+=y;if(x>=mod)x-=mod;}

int pw(int x,int y){

	int re=1;

	for(;y;y>>=1,x=1ll*x*x%mod)

		if(y&1)re=1ll*re*x%mod;

	return re;

}

void pre(){

	for(int i=fac[0]=1;i<=n;++i){

		fac[i]=1ll*fac[i-1]*i%mod;

		int lim=n/i;

		h[i].pb(1);h[i].pb(i);

		for(int j=2;j<=lim;++j){

			h[i].pb((h[i][j-1]+1ll*h[i][j-2]*(j-1)%mod)*i%mod);

		}

	}

}

void calc(int tot){

	static int st[N],tp;

	++T;tp=0;

	for(int i=1;i<=tot;++i)b[i]=0,c[i]=0;

	for(int i=1;i<=k;++i)b[bl[i]]++,c[bl[i]]+=a[i];

	int re=1,fg1=prefg1,fg2=prefg2;

	for(int i=1;i<=tot;++i){

		re=1ll*re*fac[b[i]-1]%mod;

		cnt[c[i]]++;fg1|=c[i]>1;fg2|=c[i]>2;

		if(vis[c[i]]!=T)vis[c[i]]=T,st[++tp]=c[i];

	}

	if(!fg1)re=1;

	if(fg2)re=1ll*re*preans%mod;

	for(int i=1;i<=tp;++i){

		int x=st[i];

		if(fg2)re=1ll*re*iv[x]%mod*h[x][cnt[x]]%mod;

		cnt[x]=precnt[x];

	}

	inc(ans,re);

}

void dfs(int x,int y){

	if(x==k+1){calc(y);return;}

	for(int i=1;i<=y+1;++i){

		bl[x]=i;

		dfs(x+1,max(i,y));

	}

}

int main(){

	freopen("determination.in","r",stdin);

	freopen("determination.out","w",stdout);

	scanf("%d%d",&n,&k);k=0;

	for(int i=1;i<=n;++i){

		scanf("%d",&p[i]);

		if(p[i])q[p[i]]=i;else pos[++k]=i;

	}

	for(int i=1;i<=k;++i){

		int len=1;vis[pos[i]]=1;

		for(int j=q[pos[i]];j;j=q[j])vis[j]=1,len++;

		a[i]=len;

	}

	for(int i=1;i<=n;++i)if(!vis[i]){

		int len=1;vis[i]=1;

		for(int j=p[i];j!=i;j=p[j])vis[j]=1,len++;

		cnt[len]++;prefg2|=len>2;prefg1|=len>1;

	}

	pre();

	preans=1;

	for(int i=1;i<=n;++i){

		precnt[i]=cnt[i];

		preans=1ll*preans*h[i][cnt[i]]%mod;

		iv[i]=pw(h[i][cnt[i]],mod-2);

		vis[i]=0;

	}

	dfs(1,0);

	cout<<ans<<endl;

	return 0;

}

巴特西

【JZOJ100207】【20190705】决心

题目

题解

Code

最新文章

热门文章