题意：bc round 71(中文题面)
分析（官方题解）：
根据药品之间的相互关系，我们可以构建一张图，我们对相互会发生反应的药品连边
这个图的特征，是一个环加上一些“树”（可能有多个联通块）
一个环（1,2,3,4,5……，n）m染色的方案数：递推，设第一个点颜色为1
f[I,1]表示i点颜色为1的种数，f[I,0]为颜色不为1时(不考虑n与1颜色不同)
则F[I,0]=f[i-1,0]*(m-2)+f[i-1,1]*(m-1)，F[I,1]=f[i-1,0]
那么方案数为f[n,0]*m
一个根节点颜色固定且有k个孩子的树的m染色的方案数=(m-1)^k
?? ,因为每个点的颜色只要与他的父亲颜色不同，即m-1种
因为乘法原理，一个联通块的方案数=环方案数*以环上每个点为根的树的积。多个联通块，再连乘即可
注：其实就是n个点的无向图k染色,相邻的节点颜色不一样，但是这个无向图有一个特点
就是其实无向图是由有向图（把方向去掉）变过来的，每个点的出度为1，所以不存在两个环相切(如果存在，至少存在一个点出度为2)
也就是官方题解说的，每一个连通块是由一个环和若干树组成
附上代码，这样的话时间复杂度是O（n）
#include<cstdio> #include<cstring> #include<algorithm> #include<iostream> using namespace std; typedef long long LL; const int N=1e2+5; const LL mod=1e9+7; LL dp[N][2],k; int c[N],n,T,vis[N]; void init() { dp[1][0]=0,dp[1][1]=1; for(int i=2; i<=n; ++i) { dp[i][0]=(dp[i-1][0]*(k-2)%mod+dp[i-1][1]*(k-1)%mod)%mod; dp[i][1]=dp[i-1][0]; } memset(vis,-1,sizeof(vis)); } int main() { scanf("%d",&T); while(T--) { scanf("%d%I64d",&n,&k); init(); for(int i=0; i<n; ++i) scanf("%d",&c[i]); int cnt=0; LL ans=1; for(int i=0; i<n; ++i) { if(vis[i]!=-1)continue; int x=i; while(vis[x]==-1) { vis[x]=i; x=c[x]; } if(vis[x]!=i)continue; int tmp=0,u=x; do { ++tmp; x=c[x]; }while(x!=u); ans=ans*(dp[tmp][0]*k%mod)%mod; cnt+=tmp; } cnt=n-cnt; for(int i=0;i<cnt;++i) ans=ans*(k-1)%mod; printf("%I64d\n",ans); } return 0; }
原文：http://www.cnblogs.com/shuguangzw/p/5185529.html
