CodeForces - 691E Xor-sequences 【矩阵快速幂】

题目链接

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();

}

巴特西

CodeForces - 691E Xor-sequences 【矩阵快速幂】

最新文章

热门文章