题目链接
http://codeforces.com/problemset/problem/691/E
题意
给出一个长度为n的序列，从其中选择k个数 组成长度为k的序列，因为(k 有可能 > n) 那么数字是可以重复选择的
使得 aj 属于 a1 -> ak-1 满足 aj ^ aj + 1 中二进制表示中1的个数是3的倍数
思路
很显然 当k == 1的时候，不存在 aj 属于 a1 -> a0 那么 自然是满足的 也就是说 k == 1 的时候 答案就是n
那么 k == 2 的时候 用一个二维01矩阵表示 a[i] ^ a[j] 是否满足条件 如果是 就为1
最后把这个二维矩阵的和 加起来
然后是 k >= 3 的情况
根据矩阵乘法的性质
我们知道 矩阵a * 矩阵b = 矩阵ans
ans[i][j] = a[i][1] * b[1][j] + …… + a[i][n - 1] * b[n - 1][j]
那么很显然 当 k == 3的时候
a[i][1] * b[1][j] 表示的是 数列 arr[i] arr[1] arr[j] 这个数列是否满足题目条件
加入 易知 只有当 arr[i][1] == 1 && arr[1][j] == 1的时候 才是符合的
那么其相乘起来 也是1 是一个长度为3 的满足条件的序列
由此观之，如果 k == 3 只要算 k == 2 的时候 构造的那个矩阵 的 平方 再求和 就是答案
那么 k > 3的时候 答案就是 对 k == 2 的那个矩阵 算 k - 1次幂 就可以
用矩阵快速幂优化
AC代码
#pragma comment(linker, "/STACK:102400000,102400000") #include <cstdio> #include <cstring> #include <ctype.h> #include <cstdlib> #include <cmath> #include <climits> #include <ctime> #include <iostream> #include <algorithm> #include <deque> #include <vector> #include <queue> #include <string> #include <map> #include <stack> #include <set> #include <list> #include <numeric> #include <sstream> #include <iomanip> #include <limits> #define pb push_back #define fi first #define se second #define L(on) ((on)<<1) #define R(on) (L(on) | 1) #define mkp(a, b) make_pair(a, b) #define bug puts("***bug***"); #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define CLR(a, b) memset(a, (b), sizeof(a)); #define syn_close ios::sync_with_stdio(false); cin.tie(0); #define sp system("pause"); //#define gets gets_s using namespace std; typedef long long ll; typedef long double ld; typedef long double ld; typedef unsigned long long ull; typedef pair <int, int> pii; typedef pair <ll, ll> pll; typedef vector <int> vi; typedef vector <ll> vll; typedef vector < vi > vvi; const double PI = acos(-1.0); const double EI = exp(1.0); const double eps = 1e-8; inline int read() { char c = getchar(); int ans = 0, vis = 1; while (c < '0' || c > '9') { if (c == '-') vis = -vis; c = getchar(); } while (c >= '0' && c <= '9') { ans = ans * 10 + c - '0'; c = getchar(); } return ans * vis; } const int INF = 0x3f3f3f3f; const ll INFLL = 0x3f3f3f3f3f3f3f3fll; const int maxn = (int)1e2 + 10; const int MAXN = (int)1e4 + 10; const ll MOD = (ll)1e9 + 7; int n; ll k; ll arr[maxn]; struct Matrix { ll G[maxn][maxn]; int len; Matrix () {} Matrix operator * (const Matrix& r) const { Matrix tmp; tmp.len = len; CLR(tmp.G, 0); for (int i = 0; i < len; i++) for (int j = 0; j < len; j++) for (int k = 0; k < len; k++) tmp.G[i][j] = (tmp.G[i][j] + G[i][k] * r.G[k][j]) % MOD; return tmp; } }base; Matrix pow_mod(Matrix base, ll count) { Matrix ans; ans.len = base.len; CLR(ans.G, 0); for (int i = 0; i < ans.len; i++) ans.G[i][i] = 1; while (count) { if (count & 1) ans = ans * base; base = base * base; count >>= 1; } return ans; } ll ok(ll x) { ll ans = 0; while (x) { if (x & 1) ans++; x >>= 1; } return (ans % 3 == 0); } void input() { scanf("%d%lld", &n, &k); for (int i = 0; i < n; i++) scanf("%lld", arr + i); base.len = n; for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) base.G[i][j] = ok(arr[i] ^ arr[j]); } void solve() { base = pow_mod(base, k - 1); ll ans = 0; for (int i = 0; i < base.len; i++) for (int j = 0; j < base.len; j++) ans = (ans + base.G[i][j]) % MOD; cout << ans << endl; } int main() { input(); solve(); }转载于:https://www.cnblogs.com/Dup4/p/9433064.html
相关资源：JAVA上百实例源码以及开源项目