SCU2016-06 R题矩阵快速幂优化的dp

163 阅读 0 评论 108 点赞

我是靠谱客的博主粗犷小海豚，这篇文章主要介绍SCU2016-06 R题矩阵快速幂优化的dp，现在分享给大家，希望可以做个参考。

分析：
定义 $dp[k][i][j]$ 为以 $a_i$ 开头， $a_j$ 结尾长度为 $k$ 的序列的个数，容易有一个递推，然后写成矩阵开始幂来优化掉 $k$ 就可以了。
这种矩阵快速幂主要是在后面加一个就是合法。

复制代码

#include <iostream>
#include <algorithm>
using namespace std;
class matrix
{
public:
    long long m[109][109];
    int n, mod = int(1e9) + 7;
    matrix(int x, int pos = 0) {
        n = x;
        for (int i = 0; i < x; i++) 
            for (int j = 0; j < x; j++) m[i][j] = (i == j) * pos;
    }

matrix operator*(matrix &A) {
        matrix ret(n);
        for (int i = 0; i < n; i++) 
            for (int j = 0; j < n; j++) 
                for (int k = 0; k < n; k++)
                    ret.m[i][j] = (ret.m[i][j] + m[i][k] * A.m[k][j]) % mod;
        return ret;
    }
};

long long A[109];

int main()
{
    //freopen("in.txt", "r", stdin);
    long long  n, k;
    cin >> n >> k;
    for (int i = 0; i < n; i++) cin >> A[i];
    k--;
    matrix E(n, 1), move(n);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            move.m[i][j] = (int(__builtin_popcountll(A[i] ^ A[j])) % 3 == 0);
    while (k) {
        if (k & 1) E = E * move;
        k >>= 1;
        move = move * move;
    }
    long long  ans = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            ans = (ans + E.m[i][j]) % E.mod;
    cout << ans << endl;

}

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
/*

*/

#include <iostream>
#include <algorithm>
using namespace std;
class matrix
{
public:
    long long m[109][109];
    int n, mod = int(1e9) + 7;
    matrix(int x, int pos = 0) {
        n = x;
        for (int i = 0; i < x; i++) 
            for (int j = 0; j < x; j++) m[i][j] = (i == j) * pos;
    }

    matrix operator*(matrix &A) {
        matrix ret(n);
        for (int i = 0; i < n; i++) 
            for (int j = 0; j < n; j++) 
                for (int k = 0; k < n; k++)
                    ret.m[i][j] = (ret.m[i][j] + m[i][k] * A.m[k][j]) % mod;
        return ret;
    }
};

long long A[109];

int main()
{
    //freopen("in.txt", "r", stdin);
    long long  n, k;
    cin >> n >> k;
    for (int i = 0; i < n; i++) cin >> A[i];
    k--;
    matrix E(n, 1), move(n);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            move.m[i][j] = (int(__builtin_popcountll(A[i] ^ A[j])) % 3 == 0);
    while (k) {
        if (k & 1) E = E * move;
        k >>= 1;
        move = move * move;
    }
    long long  ans = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            ans = (ans + E.m[i][j]) % E.mod;
    cout << ans << endl;

}