【JZOJ100207】【20190705】决心

傷城~ 2021-11-17 05:24 216阅读 0赞

## 题目 ##

你需要构造一个排列

初始时\$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，考虑每一个轮换
    
    ![img][]
    
    ![img][img 1]
 *  考虑一个排列\$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; }

转载于:https://www.cnblogs.com/Paul-Guderian/p/11147337.html

[img]: /images/20211116/14b4a3f96bc345079364d1cc9b7311cf.png
[img 1]: /images/20211116/ceca4e83a18f4190b7b8bf0658bea2b5.png