Description
实验室有n瓶化学药品，编号为0到n-1，你知道第i瓶只有和第c[i]瓶放在一起才会发生爆炸。为了整理实验室，你需要将他们装进k个丌同的盒子里。显然，为了你的生命安全，你丌能把两瓶会造成爆炸的药品放进同一个箱子。你希望计算出有多少中丌同的方案。为了降低难度，你只需要将答案mod 1000000007。
Input
第一行一个整数T，表示有T组测试数据。
对于每组数据
第一行两个整数n，k
第二行n个整数表示c[i]
Output
对于每组数据输出一行一个整数。
Sample Input
3
3 3
1 2 0
4 3
1 2 0 0
3 2
1 2 0
Sample Output
6
12
0
Data Constraint
1<=T<=50 1<=n<=100 2<=k<=1000 0 < Ci < n ,i≠c[i]
对于30%的数据T,n,k<=50
.
.
.
.
分析
mix：
把不能放一起的药连一条边。
最后会得到若干环套树（一个环，每个节点可以是一棵树），也可能退化成一棵树，我们可以理解成环上只有一个节点的环套树。
现在要将其k染色，使得有边相连的节点颜色不同。
我们可以DP求得一个环的方案数，那么对于环上连出的一棵树，它的方案数显然是(k-1)^Size（这里的Size是不算在环上的那个节点的这课树的节点数）。
最后只要把环的方案数*所有树的方案数的乘积就是最终答案。
.
.
.
.
.
程序：
#include<iostream>
#include<string.h>
using namespace std;
long long ans,a[101],d[101],f[101][3];
int n,k,t,inf=1000000000,mo=1000000007;
int main()
{
cin>>t;
for (int i=1;i<=t;i++)
{
memset(a,0,sizeof(a));
memset(d,0,sizeof(d));
memset(f,0,sizeof(f));
cin>>n>>k;
for (int i=0;i<=n-1;i++)
{
cin>>a[i];
d[i]=inf;
}
f[0][1]=1;
f[1][0]=k-1;
for (int i=2;i<=n;i++)
{
f[i][0]=(f[i-1][1]*(k-1)+f[i-1][0]*(k-2))%mo;
f[i][1]=f[i-1][0];
}
ans=1;
for (int i=0;i<=n-1;i++)
if (d[i]==inf)
{
int x=i;
while (d[x]==inf)
{
d[x]=i;
x=a[x];
}
if (d[x]!=i) continue;
int y=x;
long long tot=1;
x=a[x];
while (x!=y)
{
tot++;
x=a[x];
}
ans=ans*(f[tot][1]*k%mo)%mo;
n-=tot;
}
for (int i=1;i<=n;i++)
ans=(ans*(k-1))%mo;
cout<<ans<<endl;
}
}