讨论 / 我来救你们了
sei 2017-01-23 22:29:09
点我顶贴 收藏 删除
第三题——Mixing Chemicals

题目描述

实验室有n瓶化学药品,编号为0到n-1,你知道第i瓶只有和第c[i]瓶放在一起才会发生爆炸。为了整理实验室,你需要将他们装进k个不同的盒子里。显然,为了你的生命安全,你不能把两瓶会造成爆炸的药品放进同一个箱子。你希望计算出有多少中不同的方案。为了降低难度,你只需要将答案mod 1000000007。

输入

第一行一个整数T,表示有T组测试数据。

对于每组数据

第一行两个整数n,k

第二行n个整数表示c[i]

输出

对于每组数据输出一行一个整数。

样例输入

3

3 3

1 2 0

4 3

1 2 0 0

3 2

1 2 0

样例输出

6

12

0

数据范围限制

【数据范围】

1<=T<=50

1<=n<=100

2<=k<=1000

0<=c i < n,i≠c[i]

对于30%的数据T,n,k<=50

终于将这鬼题AK了(多亏了林大犇)的指导。

我们可以将不能放在一起的瓶子,看成两个点连成一条边(这样就形成了几个环套树也就是连通块),可以填k种颜色。

然后我们求出每个点可以填涂的颜色的数量,设f[i,0/1]表示为第i个点,0为填除黑色外的颜色,1为填黑色。

dp式为 f[i,0]:=(f[i-1,1]* (k-1)+f[i-1,0]*(k-2)) mod mo; f[i,1]:=f[i-1,0] mod mo;

mo为要取摸的数

然后我们将每个点在哪个环求出来,在求出连通块的个数,然后ans:=ans* (f[lt,1]*k mod mo)mod mo; lt为当前循环的搜到的连通块的个数

最后 n:=n-z; for i:=1 to n do ans:=ans*(k-1) mod mo; writeln(ans); 求出将每个连通块的填颜色的个数相乘就求出ans,最后输出就好了。

代码如下:

const mo=1000000007;

var t,i,n,k,w,j:longint;

lt,ans,temp,z:int64;

f:array[0..100,0..1]of int64;

a,b:array[0..100]of longint;

begin

assign(input,'mix.in');

assign(output,'mix.out');

reset(input);

rewrite(output);

readln(t);

for j:=1 to t do

begin

fillchar(a,sizeof(a),#0);

fillchar(b,sizeof(b),#0);

readln(n,k);

f[1,0]:=k-1;

f[0,1]:=1;

for i:=2 to n do

begin

f[i,0]:=(f[i-1,1]*(k-1)+f[i-1,0]*(k-2)) mod mo;

f[i,1]:=f[i-1,0] mod mo;

end;

for i:=0 to n-1 do

begin

read(a[i]);

b[i]:=233;

end;

z:=0;

ans:=1;

readln;

for i:=0 to n-1 do

if b[i]=233 then

begin

temp:=i;

while b[temp]=233 do

begin

b[temp]:=i;

temp:=a[temp];

end;

if b[temp]<>i then continue;

lt:=0;

w:=temp;

repeat

inc(lt);

temp:=a[temp];

until temp=w;

ans:=ans*(f[lt,1]*k mod mo)mod mo;

z:=z+lt;

end;

n:=n-z;

for i:=1 to n do ans:=ans*(k-1) mod mo;

writeln(ans);

end;

close(input);

close(output);

end.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

今天做提高模拟题,一大堆0分的人(当然也有我),正是欲哭无泪啊!

感觉以我现在的水平,做两万年都做不出来(没有大神的指导),我还是先回松山湖修炼修炼吧。

版权声明:谁转谁是猪猪猪猪猪猪猪猪猪猪猪猪猪猪猪猪猪猪猪猪猪猪猪猪猪猪猪猪猪猪猪猪猪

顶1 踩0

查看更多回复
提交回复