【NOIP2013模拟9.29】Mixing Chemicals

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;} }

转载于:https://www.cnblogs.com/YYC-0304/p/9499918.html

总结

以上是生活随笔为你收集整理的【NOIP2013模拟9.29】Mixing Chemicals的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。