存后三個數的暴力略。

\(f_{x,y}\)：從左往右選數，當前選的最后一個數在 \(x\)，選的倒數第二個數在 \(y\) 的合法方案數。

這時候我們不得不思考我們拼接是否合法的問題，首先 \(x,y,z,i\) 不合法我們用了一下容斥，但是容斥減去的東西是對的嗎？我們減去了 \(x,y,z,i\) 不合法，但是卻用了 \(f_{i,z}\)，\(f\) 只保證了 \(z\) 前合法，而 \(i,z\) 拼接上 \(y\) 這一步合法嗎？我們發現實際上 \(a_x\oplus a_y\oplus a_z\oplus a_i=s\) 與 \(a_i\) 互不相同的已經限制了 \(y\) 前合法，而到 \(x\) 第一次不合法。

現在到了維護時間！這是我喜歡這題的地方，他是很好的前綴和練習題。

總之就是考慮新的 \(f_{x,y}\) 對這三個數組的影響。

\(qz_x\) 可以直接處理，因為轉化為了一維偏序。

容易發現在枚舉 \(x\) 的時候處理 \(t_{x,m}\)，現在復雜度還是很炸。

trick：增量處理含義有偏序的數組。

其中

因為枚舉 \(i,p,m\) 是冗雜的，且對 \(i,p\) 限制相對 \(m\) 更緊密，然后發現只枚舉 \(i<p\) 就可以更新 \(d_{p,m}\) 數組，也轉化為了一維偏序。

總結：

此題允許 \(O(n^2)\)，所以一維偏序直接做的時間復雜度是對的，所以化到一維就好了。（最底層的是每個形如 \(j<i\) 的 \(\{j,i\}\) 組合只會貢獻一次，但是我們每次是用剛出來的 \(f_{x,j}\) 去貢獻）

#include<bits/stdc++.h>
using namespace std;
const int QAQ=4100,mo=998244353;
int n,m,s,a[QAQ],f[QAQ][QAQ],d[QAQ][QAQ],qz[QAQ],t[QAQ][QAQ],ans;
#define jia(x,y) x=((x)+(y))%mo;
signed main()
{
	cin>>n>>m>>s;
	for(int x=1;x<=n;x++)
	{
		cin>>a[x],f[x][0]=1;
		for(int y=0;y<x;y++)
		{
			if(y)
				f[x][y]=(qz[y]-t[y][a[x]^a[y]^s]+mo)%mo,
				jia(d[x][a[y]^a[x]],f[x][y]);
			jia(qz[x],f[x][y]);
		}
		for(int i=0;i<(1<<m);i++) t[x][i]=(t[x-1][i]+d[x-1][i])%mo;
		ans=(ans+qz[x])%mo;
	}
	cout<<ans;
	return 0;
}

\(f_i\)：\([1,i]\) 合法方案數。
\(f_i=f_{i-1}×m-不合法方案數\)
不合法方案數是 \(f_{i-k}\) 嗎？
這個和第一題一樣，我們直接使用 \(f_{i-k}\) 是不可以的，因為我們相當于沒有告訴 DP 數組 \([i-k+1,i]\) 的情況。
那么我們思考一下什么時候 \([i-k+1,i-1]\) 會使得 \(f_{i-k}\) 本身不合法（當然我們必須在第一次不合法的時候計數，所以我們需要使得 \(f_{i-k}\) 合法，才能構造不合法的字符串）。
推一下性質：
手玩一下臨界情況，發現 \([i-k+1,i-1]\) 始終包含 \(i-k\) 和 \(i-2*k\) ，所以我們欽定這兩個數不相等即可，同時相等也必然不合法。
所以不合法方案數是 \((m-1)f_{i-k-1}\)。
注意前 \(2k\) 預處理。