松鼠配对？

题意：

给出一张无向图，有n(<=100)个点，m条边，第i个点上一开始有ai个特殊点，这些特殊点一个单位时间移动一次，求移动T(<=1e9)次后，每个点上的点对的期望值(答案对1e9+7)取模（假如一个点上有4个特殊点，那么这个点上就有6个点对）。

题解：

首先看到T的数据范围，这个提示的是要用log级别的算法，很容易就想到了矩阵，现在的问题就是验证矩阵是否可行。

很容易知道初始矩阵是n * n的，那么这个矩阵表示的是什么？很容易知道是表示概率，因为刚好满足了乘法原理和加法原理，到此说明矩阵是可行的。

用矩阵就可以知道一个点到达另外一个点的概率，而E = P * w，现在可以很容易得到一个点到达另外一个点的期望值。

那么一对人的贡献

ans += P[u] * ai[u] * P[v] * ai[v] (u != v)

ans += ai[u] * (ai[u] - 1) / 2 * P[u] * P[u] (u == v)

代码：

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

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

#define LL long long

const int N = 1e3 + 7;

const int mod = 1e9 + 7;

struct Matrix

{

    LL map[107][107];

} F;

LL inv[N], ans, a[N][N], sum[N];

int n, c[N][N], num[N], T;

Matrix Mul (Matrix a, Matrix b)

{

    Matrix ret;

    memset (ret.map, 0, sizeof ret.map);

    for (int i = 1; i <= n; ++ i)

        for (int j = 1; j <= n; ++ j)

            for (int k = 1; k <= n; ++ k)

                ret.map[i][j] = (ret.map[i][j] + a.map[i][k] * b.map[k][j] % mod) % mod;

    return ret;

}

Matrix Pow (Matrix x, int cnt)

{

    Matrix ret;

    memset (ret.map, 0, sizeof ret.map);

    for (int i = 0; i <= n; ++ i) ret.map[i][i] = 1;

    while (cnt)

    {

        if (cnt & 1) ret = Mul(ret, x);

        x = Mul(x, x);

        cnt >>= 1;

    }

    return ret;

}

LL pow (LL x, int n)

{

    LL ret = 1;

    while (n)

    {

        if (n & 1) ret = ret * x % mod;

        x = x * x % mod;

        n >>= 1;

    }

    return ret;

}

int main ()

{

    scanf ("%d%d", &n, &T);

    for (int i = 1; i <= n; ++ i) scanf ("%d", &num[i]);

    for (int i = 1; i <=1000; ++ i) inv[i] = pow (i, mod - 2);

    for (int i = 1; i <= n; ++ i)

        for (int j = 1; j <= n; ++ j)

            scanf ("%d", &c[i][j]);

    for (int i = 1; i <= n; ++ i)

    {

        int cnt = 0;

        for (int j = 1; j <= n; ++ j) cnt += c[i][j];

        for (int j = 1; j <= n; ++ j) a[i][j] = c[i][j] * inv[cnt];

    }

    if (T != 1)

    {

        for (int i = 1; i <= n; ++ i)

            for (int j = 1; j <= n; ++ j)

                F.map[i][j] = a[i][j];

        F = Pow (F, T);

        for (int i = 1; i <= n; ++ i)

            for (int j = 1; j <= n; ++ j)

                a[i][j] = F.map[i][j];

    }

    for (int i = 1; i <= n; ++ i)

    {

        for (int j = 1; j <= n; ++ j)

            sum[j] = (sum[j - 1] + a[j][i] * num[j] % mod) % mod;

        for (int A = 1; A <= n; ++ A)

        {

            ans = (ans + num[A] * (num[A] - 1) * inv[2] % mod * a[A][i] % mod * a[A][i] % mod) % mod;

            ans = (ans + (sum[n] - sum[A] + mod) % mod * a[A][i] % mod * num[A] % mod) % mod;

        }

    }

    cout << ans << endl;

    return 0;

}

总结：

1.这个题个人觉得不是很难，但是暴露出概率和期望确实学得不是一般的水啊~

2.这个矩阵就写得很蠢了，明明可以直接用数组写，而且还可能更快。

相关知识

狗子配对，聪明小狗配对成功
万花宠物松鼠攻略 万花宠物任务
宠物配对平台,宠物配对app
如何训练驯化金花松鼠
一只松鼠可以打败什么动物
猫咪配对,哪里可以给猫咪配对
鸽子配对笼
鸽子配对笼子
土狗配对，聪明小狗跟随大狗耍无赖，成功配对母狗
动物配对最新版下载

网址: 松鼠配对？ https://www.mcbbbk.com/newsview1025453.html