【DP+矩阵加速】CF691 E

- 日理万妓 2024-03-23 20:10 57阅读 0赞

[Problem - 691E - Codeforces][]

题意：

![2e293999291340b5bac9a8c72785076c.png][]

思路：

有人只会暴力DP忘记矩阵快速幂怎么写了

![3908f81bdf0641acb960f0cf2de58e5a.png][]

![5dcab5d9f8844df5b27ecbb54eec464b.png][]

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using i64 = long long;
    
    using namespace std;
    
    const int N = 1e2 + 10;
    const int mod = 1e9 + 7;
    
    int n, k;
    int a[N];
    
    struct Matrix {
        int m[N][N];
        void init() {
            for (int i = 1; i <= n; i ++) {
                m[i][i] = 1;
            }
        }
        void clr() {
            for (int i = 1; i <= n; i ++) {
                for (int j = 1; j <= n; j ++) {
                    m[i][j] = 0;
                }
            }
        }
    };
    
    Matrix Mul(Matrix a, Matrix b) {
        Matrix ans;
        ans.clr();
        for (int i = 1; i <= n; i ++) {
            for (int j = 1; j <= n; j ++) {
                for (int k = 1; k <= n; k ++) {
                    ans.m[i][j] += a.m[i][k] * b.m[k][j];
                    ans.m[i][j] %= mod;
                }
            }
        }
        return ans;
    }
    
    Matrix ksm(Matrix a, int b) {
        Matrix res;
        res.clr();
        res.init();
        while(b) {
            if (b & 1) res = Mul(res, a);
            a = Mul(a, a);
            b >>= 1;
        }
        return res;
    }
    
    void solve() {
        cin >> n >> k;
        for (int i = 1; i <= n ;i ++) {
            cin >> a[i];
        }
    
        Matrix Base;
        Base.clr();
        for (int i = 1; i <= n; i ++) {
            for (int j = 1; j <= n; j ++) {
                if (__builtin_popcountll(a[i] ^ a[j]) % 3 == 0) {
                    Base.m[i][j] = 1;
                }
            }
        }
    
        Base = ksm(Base, k - 1);
        int ans = 0;
        for (int i = 1; i <= n; i ++) {
            for (int j = 1; j <= n; j ++) {
                ans += Base.m[i][j];
                ans %= mod;
            }
        }
        cout << ans << "\n";
    }
    signed main() {
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
        
        int t = 1;
        //cin >> t;
        while(t --) {
            solve();
        }
        return 0;
    }

[Problem - 691E - Codeforces]: https://codeforces.com/problemset/problem/691/E
[2e293999291340b5bac9a8c72785076c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/520f10c6a6f847fb9ba1de13bc60d95a.png
[3908f81bdf0641acb960f0cf2de58e5a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/8f79412c5dbe4c7eabb4d286ade6e8e9.png
[5dcab5d9f8844df5b27ecbb54eec464b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/3519f9188ee943d8969b515d2930c9f6.png