题目简述
选择的学校编号依次为 \(p1, p2, p3, ..., pk(1 ≤ p1 < p2 < ... < pk ≤ n)\)，若存
在 \(i(1 ≤ i ≤ k − 3)\) 使得 $ a_{p_i} ⊕ a_{p_{i+1}} ⊕ a_{p_{i+2}} ⊕ a_{p_{i+3}} = s $，则该序列不合法。
求在所有 \(2^{n − 1}\) 个可能的序列中问有多少个序列合法。
你只需要输出答案 \(mod \ 998244353\) 之后的结果即可。
分析 & 性质
大力容斥没有前途。
-
考虑dp: \(dp[i][j][k] \leftarrow dp[j][k][l]\) 判断不合法，\(3D0D\) 转移， 期望60pts。
-
有个性质，\(i(i, j, k, l, i')\)不合法时 \(i\) 和 \(i'\) 不等.
-
然后压状态 \(dp[i][j] \leftarrow \sum \limits _{j, k} ^ {} dp[j][k] - \sum \limits _{i⊕j⊕k⊕l \ne S} ^ {}dp[k][l]\)
-
思路就是容斥，然后正确性由性质保证。从 \(\sum \limits _{j, k} ^ {} dp[j][k]\) 中去掉 \(l\) 不合法的情况，减去 \(\sum \limits _{i⊕j⊕k⊕l \ne S} ^ {}dp[k][l]\) ,但是在一般情况下难以保证 \(j\) 合法，但是性质导致一定不存在第二个i，so, \(j\) 一定合法, 容斥时，可保证i不合法且j, k, l都合法的情况被减去。
最终思路
- 考虑拆贡献，可发现对于一个 \(dp[i][j]\) , \(dp[k][l]\) 只被贡献一次, 开桶统计即可； 对于dp[j][k]，前缀和优化即可， \(2D0D\)， 期望100pts。
(一开始写的是容斥 \(n^3\) 还没上面那个60好写，就是没发现互不相同的性质)