本文共 1946 字，大约阅读时间需要 6 分钟。

传送门：

题目大意：

统计满足下列条件的数列的方案数:

• 非空
• 严格递增
• 任意连续三个元素的异或和不为 \(0\)
• 元素小于等于给定的 \(n\)

分析：

\(f[i]\) 表示以 \(i\) 为尾的方案数。

考虑状态转移：

• 如果 \(f[i]\) 只有一个元素，自然属于一种方案。
• 如果 \(i\) 的上一个数是 \(j ~ (j \in [1,i-1])\)
  • \(i \oplus j >= j\) 时，直接转移即可 \(f[i]+=f[j]\)
  • 否则， \(f[i]+=f[j]-f[j \oplus i]\)

写出更为一般化的公式就是：
\(f[i]=\sum_{u=1}^{i-1} f[u] - \sum_{j=1}^{i-1} f[i \oplus j]\)，这里的 \(j\) 满足 \((j > i \oplus j)\)

我们记 \(highbit(x)\) （是我乱起的）为二进制中 \(x\) 除了最高位为 \(1\) 其余全部清 \(0\) 所对应的数，例如：\(highbit(11001)=10000\)

注意到 \(j\) 与 \(i\) 必须位数相等（充分必要条件）。
因此，我们可以得到更为精确的 \(j\) 的范围 \([highbit(i),i-1]\)

记 \(k=i\oplus j\) ，我们只需找到一个快速统计 \(k\) 的办法就好了。

举两个例子（二进制）：
\(i=10100,故~j=10000-10011\) ，对应的 \(k\) 为 \(100-111\) （不一定是依次对应的）。

\(i=101010,故~j=1000000-101001\) ，
对应的 \(k\) 为 \(1000-1111\)，以及 \(10-11\) （不一定是依次对应的）。

从中我们发现了规律：
记 \(t=i-highbit(i)\) ，然后每一次取 \(t\) 的 \(highbit\) ，区间 \([highbit(t),highbit(2t-1)]\) 都是满足的，我们依次统计就好了。

证明挺简单的，就留作习题吧。

我自己乱搞了一个求 \(highbit(x)\) 的算法：
就是求 \(2^{\lfloor log_2x \rfloor}\) 即可。

如果感觉不太好懂可以用下面的打表程序试试：

#include<bits/stdc++.h>using namespace std;const int N=1e6+6;int highbit[N];void init(){	for(int i=2;i<N;i++){		highbit[i]=highbit[i/2]+1;		}	for(int i=2;i<N;i++)		highbit[i]=1LL<<highbit[i];	highbit[1]=1;}void get(int x){	vector<int> v;	while(x) v.push_back(x%2), x>>=1;	reverse(v.begin(),v.end());	for(auto i:v) cout<<i;	cout<<' '; 	}int main(){	init();	int i; cin>>i;	for(int j=highbit[i];j<=i-1;j++)		get(j^i), puts("");	return 0;}

原题代码：

#include<bits/stdc++.h>using namespace std;const int N=1e6+6;const int mod=998244353;long long f[N],s[N];int highbit[N];void init(){	for(int i=2;i<N;i++){		highbit[i]=highbit[i/2]+1;		}	for(int i=2;i<N;i++)		highbit[i]=1LL<<highbit[i];	highbit[1]=1;}int main(){	init();	int n; cin>>n;		cerr<<highbit[N-1];	for(int i=1;i<=n;i++){		auto &v=f[i];		v=1;		v=(v+s[i-1])%mod;		int t=i;		t-=highbit[t];		while(t){			int x=highbit[t];			v=(v-(s[(x<<1)-1]-s[x-1])+mod)%mod;			t-=x;		}		s[i]=(s[i-1]+v)%mod;		}	cout<<s[n]<<endl;		return 0;}