题意：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+;
const LL mod=1e9+;
LL dp[N][],k;
int c[N],n,T,vis[N];
void init()
{
dp[][]=,dp[][]=;
for(int i=; i<=n; ++i)
{
dp[i][]=(dp[i-][]*(k-)%mod+dp[i-][]*(k-)%mod)%mod;
dp[i][]=dp[i-][];
}
memset(vis,-,sizeof(vis));
}
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d%I64d",&n,&k);
init();
for(int i=; i<n; ++i)
scanf("%d",&c[i]);
int cnt=;
LL ans=;
for(int i=; i<n; ++i)
{
if(vis[i]!=-)continue;
int x=i;
while(vis[x]==-)
{
vis[x]=i;
x=c[x];
}
if(vis[x]!=i)continue;
int tmp=,u=x;
do
{
++tmp;
x=c[x];
}while(x!=u);
ans=ans*(dp[tmp][]*k%mod)%mod;
cnt+=tmp;
}
cnt=n-cnt;
for(int i=;i<cnt;++i)
ans=ans*(k-)%mod;
printf("%I64d\n",ans);
}
return ;
}