首页 > 代码库 > Codeforces 691E Xor-sequences(思维)
Codeforces 691E Xor-sequences(思维)
题目链接 Xor-sequences
利用矩阵加速。
先预处理出当序列长度为2的时候的方案数。
也就是说这个序列起点是a[i]终点是a[j]且中间没有任何元素。
但是所求的k很大,序列长度远远不止2。这个时候就要考虑乘法原理。
然后利用矩阵乘法来模拟乘法原理,那么就用到了矩阵快速幂。
#include <bits/stdc++.h> using namespace std; #define rep(i, a, b) for(int i(a); i <= (b); ++i) struct Matrix{ long long arr[105][105];} init, unit; long long k, ret, mod = 1e9 + 7; long long a[105]; int n; Matrix Mul(Matrix a, Matrix b){ Matrix c; rep(i, 1, n) rep(j, 1, n){ c.arr[i][j] = 0; rep(k, 1, n) (c.arr[i][j] += (a.arr[i][k] * b.arr[k][j] % mod)) %= mod; } return c; } Matrix Pow(Matrix a, long long k){ Matrix ret(unit); for (; k; k >>= 1, a = Mul(a, a)) if (k & 1) ret = Mul(ret, a); return ret; } inline long long check(long long x){ int ret = 0; for (; x; x >>= 1) ret += (x & 1); return ret % 3 == 0; } int main(){ scanf("%d%lld", &n, &k); rep(i, 1, n) unit.arr[i][i] = 1; rep(i, 1, n) scanf("%lld", a + i); rep(i, 1, n) rep(j, 1, n) init.arr[i][j] = check(a[i] ^ a[j]); Matrix Ans = Pow(init, k - 1); ret = 0; rep(i, 1, n) rep(j, 1, n) (ret += Ans.arr[i][j]) %= mod; printf("%lld\n", ret); return 0; }
Codeforces 691E Xor-sequences(思维)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。