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;
}