I. Xor-sequences-dp-矩阵快速幂

约定不等于承诺〃 2022-10-15 00:43 151阅读 0赞

[链接][Link 1]

### Xor-sequences ###

*  大意
 *  思路
 *  code1
 *  优化代码

# 大意 #

**题面**

exclusive or operation ：异或运算

定义  x 1 ,     x 2 ,     . . . ,     x k x\_1,  x\_2,  ...,  x\_k x1,  x2,  ...,  xk 是一个异或序列，异或运算  
 x o r ( x i , x i + 1 ) xor(x\_i ,x\_\{i+1\}) xor(xi,xi\+1) 的结果在二进制表示下‘1’的个数是三的倍数。

**输入**  
序列  x 1 ,     x 2 ,     . . . ,     x n x\_1,  x\_2,  ...,  x\_n x1,  x2,  ...,  xn 和 k，其中n和k最大达到long long 级别的数量级

**输出**  
符合异或序列的子序列个数

# 思路 #

如果转移状态不变，可以使用矩阵优化  
n有100个数，先预处理，判断这100个数，两两异或运算是否可以连在一起（预处理）。

# code1 #

#include <bits/stdc++.h>
    using namespace std;
    const int N = 105;
    const int mod = 1e9+7;
    typedef long long ll;
    ll n, k;
    ll arr[N];
    
    struct Mat
    { 
    	ll num[N][N];
    };
    
    Mat mul(Mat a, Mat b)
    { 
    	Mat ans;
    	for(int i = 1; i <= n; ++i)
    		for (int j = 1; j <= n; ++j)
    		{ 
    			ans.num[i][j] = 0;
    			for (int k = 1; k <= n; ++k){ 
    				ans.num[i][j] = (ans.num[i][j] + (a.num[i][k] * b.num[k][j])%mod)%mod;
    			}
    		}
    	return ans;
    }
    
    Mat Pow(Mat a, ll k)
    { 
    	Mat ans;
    
    	memset(ans.num, 0, sizeof(ans.num));
    	for(int i = 1; i <= n; i++) ans.num[i][i] = 1;
    	while(k)
    	{ 
    		if(k&1) ans = mul(ans, a);
    		a =  mul(a, a);
    		k >>= 1;
    	}
    	return ans;
    }
    
    inline ll count(ll x)
    { 
    	ll cnt = 0;
    	while(x){ 
    		if(x%2==1) cnt++;
    		x >>= 1;
    	}
    	return cnt;
    }
    int main()
    { 
    	Mat A;
    	memset(A.num, 0, sizeof(A.num));
    	scanf("%lld %lld", &n, &k);
    	for (int i = 1; i <= n; ++i) scanf("%lld", &arr[i]);
    	for (int i = 1; i <= n; ++i){ 
    		for (int j = 1; j <= n; ++j){ 
    			A.num[i][j] = (count(arr[i]^arr[j])% 3 == 0);
    		}
    	}
    	A = Pow(A, k-1);
    	ll ans = 0;
    	for(int i = 1; i <= n; i++){ 
    		for(int j = 1; j <= n; j++){ 
    			ans = (ans + A.num[i][j]) % mod;
    		}
    	}
    	printf("%lld\n", ans);
    	return 0;
    }

问题出现在矩阵乘法上，模的时候没有加上自身。

ans.num[i][j] = (ans.num[i][j] + (a.num[i][k] * b.num[k][j])%mod)%mod;

# 优化代码 #

使用inline 函数应该可以加快速度

这个函数再写一遍，

inline int count(ll x)
    { 
    	int cnt = 0;
    	while(x)
    	{ 
    		if(x%2==1) cnt++;
    		x >>= 1;
    	}
    	return cnt;
    }

或者

#define lowbit(x) ((x)&-(x))
    inline int count(ll x)
    { 
    	int res=0;
    	while(x)
    		x^=lowbit(x), ++res;
    	return res;
    }

[Link 1]: https://codeforces.com/group/vFwRVj9WjO/contest/328371/problem/I