题解：qoj 9479

因为限制长成了环形的鬼样子，导致一个一个数地填维护限制非常困难，必须将填的过程对每个数同时进行。但是注意到

a_i + (a_{i-1} \& a_{i+1})

的样子很二进制，可以发现该式上

a

最低位只有限地影响得数最低几位。因此有逐位确定的想法，可以在当前最低位上，对每个数的该位进行填，以凑出

M

的这一位。那么就得到了分讨

M

最低位 + 递归的做法。其中每三位凑出

1

的情况，相当于填

0/1

环列，不能有连续的三个

1

和连续的两个

0

。可以递推，矩阵乘法加速。

CPP

#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353;
struct Matrix {
	int a[3][3];
}I, ori, trans;
Matrix operator *(const Matrix &a,const Matrix &b){
	Matrix ret;
	for(int i=0;i<=2;i++) for(int j=0;j<=2;j++){
		ret.a[i][j] = 0;
		for(int k=0;k<=2;k++) ret.a[i][j] = (ret.a[i][j] + 1ll * a.a[i][k] * b.a[k][j] % mod) % mod;
	}
	return ret;
}
Matrix ksm(Matrix s,int cnt){
	Matrix ret = I;
	while(cnt){
		if(cnt & 1) ret = ret * s;
		s = s * s;
		cnt >>= 1;
	}
	return ret;
}

int N, M, S;

map<int,int> f;
int dfs(int M){
	if(f.find(M) != f.end()) return f[M];
	if(M == 0) return 1;
	if(M == 1) return S;
	int s;
	if(M & 1) s = 1ll * dfs((M-1)/2) * S % mod;
	else s = (1ll * dfs(M/2) + dfs(M/2-1)) % mod;
	f[M] = s;
	return s;
}

int main(){
	I.a[0][0] = 1, I.a[1][1] = 1, I.a[2][2] = 1;
	trans.a[1][0] = 1, trans.a[2][1] = 1, trans.a[0][2] = 1, trans.a[1][2] = 1;
	ori.a[0][2] = 1;
	
	scanf("%d%d",&N,&M);
	ori = ori * ksm(trans, N-3);
	S = ori.a[0][2];
	ori = ori * trans;
	S = (1ll * S + ori.a[0][2] + ori.a[0][1]) % mod;
	ori = ori * trans;
	S = (1ll * S + ori.a[0][1] + ori.a[0][0]) % mod;
	
	printf("%d\n",dfs(M));
	
	return 0;
}

文章操作

相关推荐

评论

题解：qoj 9479