CF691E Xor-sequences 题解

题目链接：CF691E Xor-sequences

题意：给定大小为 $n$ 的集合 $\{a_1,\dots,a_n\}$，从集合中选择 $k$ 个数组成一个序列 $x_1 , \dots , x_k$ (可以重复选择)，使得序列满足 $x_i$ 与 $x_i +1$ 异或的二进制中 $1$ 的个数是 $3$ 的倍数

问长度为 $k$ 的满足条件的序列的种数，答案对 $10^9 + 7$取模。

$1\le n\le 100,~1\le k,a_i \le 10^{18}$

设 $f_{i,j}$ 表示序列长度为 $i$ 且最后一个数为 $a_j$ 时的方案数，则

$$f_{0,j}=1 \\\\f_{i,j}=\sum_{1\le k \le n}f_{i-1,k}\times g_{k,j}$$

其中 $g_{k,j}$ 表示 $\left[3 \mid (a_k \oplus a_j)_{\texttt{ 2进制下1的数量}}\right]$

可以发现这个形式就是矩阵乘法的定义式

考虑矩阵快速幂优化dp

时间复杂度 $O(n^3 \log k)$

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)()
typedef vector< vector<int> > mat;

const int mod=1e9+7;
void add(int &x,int y){x+=y;if(x>=mod)x-=mod;}
mat mul(mat A,mat B)
{
    int n=A.size(),m=A[0].size(),p=B[0].size();
    mat C(n,vector<int>(p));
    for(int k=0; k<m; k++)
        for(int i=0; i<n; i++)  
            for(int j=0; j<p; j++)
                add(C[i][j],A[i][k]*B[k][j]%mod);
    return C;
}
mat qpow(mat A,int k)
{
    int n=max(A.size(),A[0].size()); 
    mat B(n,vector<int>(n));
    for(int i=0; i<n; i++) B[i][i]=1;
    while(k)
    {
        if(k&1) B=mul(B,A);
        A=mul(A,A); k>>=1;
    }
    return B;
}
bool check(int x)
{
    int res=0;
    while(x)++res,x-=(x&(-x));
    return res%3==0;
}
int n,k,a[115]; 
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> k;
    mat A(1,vector<int>(n)),B(n,vector<int>(n));
    for(int i=0; i<n; i++)
        cin >> a[i],A[0][i]=1;
    for(int i=0; i<n; i++)
        for(int j=i; j<n; j++)
            if(check(a[i]^a[j]))
                B[i][j]=B[j][i]=1;
    B=qpow(B,k-1); A=mul(A,B);
    int res=0;
    for(int i=0; i<n; i++)
        add(res,A[0][i]);
    cout << res << '\n';
    return 0;
}