BZOJ传送门

洛谷传送门

---

解析：

将$i$向$a[i]$连边，那么我们得到一个内向基环树森林（环上点没有外向边）。

显然环外的骰子直接分配极大值就行了。

对于环内的骰子我们有这样一种策略：选择一个点，向父亲方向依次放下1~n的值，再选择它的父亲，向父亲方向依次放下n+1 ~ 2n。如此重复直到填满。

可以证明这样的策略填出来的环内概率$\ge \frac{1}{2}$，而且只有当环长为$3$，骰子面数为$4$的时候会出现$\frac{1}{2}$，按照BZOJ上样例来特判就行了。

---

代码：

#include<bits/stdc++.h> #define ll long long #define re register #define gc getchar #define cs const namespace IO{ template<typename T> inline T get(){ re char c; while(!isdigit(c=gc()));re T num=c^48; while(isdigit(c=gc()))num=(num+(num<<2)<<1)+(c^48); return num; } inline int getint(){return get<int>();} } using namespace IO; using std::cerr; using std::cout; cs int N=202; cs int sp[4][5]={ {}, {0,1,3,10,11}, {0,2,7,8,9}, {0,4,5,6,12}, }; int n,m; int a[N]; int ans[N][N]; int q[N],qn; int d[N]; bool vis[N]; inline void top_sort(){ int num=n*m; for(int re i=1;i<=n;++i)if(!d[i])q[++qn]=i; for(int re i=1,u;i<=qn;++i){ vis[u=q[i]]=true; for(int re i=1;i<=m;++i)ans[u][i]=num--; if(!--d[a[u]])q[++qn]=a[u]; } for(int re i=1,j;i<=n;++i)if(!vis[i]){ for(j=i,qn=0;!vis[j];j=a[j])vis[q[++qn]=j]=true; if(qn<=2)puts("0"),exit(0); num-=qn*m; if(qn==3&&m==4){ ans[q[1]][1]=sp[1][1]+num; ans[q[1]][2]=sp[1][2]+num; ans[q[1]][3]=sp[1][3]+num; ans[q[1]][4]=sp[1][4]+num; ans[q[2]][1]=sp[2][1]+num; ans[q[2]][2]=sp[2][2]+num; ans[q[2]][3]=sp[2][3]+num; ans[q[2]][4]=sp[2][4]+num; ans[q[3]][1]=sp[3][1]+num; ans[q[3]][2]=sp[3][2]+num; ans[q[3]][3]=sp[3][3]+num; ans[q[3]][4]=sp[3][4]+num; } else { for(int re cnt=1,i=1;cnt<=m;i=i==1?qn:i-1,++cnt){ ans[q[i]][cnt]=++num; for(int re j=i==1?qn:i-1;j^i;j=j==1?qn:j-1) ans[q[j]][cnt]=++num; } num-=qn*m; } } } signed main(){ n=getint(),m=getint(); for(int re i=1;i<=n;++i){ ++d[a[i]=getint()]; if(a[i]==i)puts("0"),exit(0); } top_sort(); for(int re i=1;i<=n;++i) for(int re j=1;j<=m;++j) cout<<ans[i][j]<<(j==m?'\n':' '); return 0; }