题意
给定 \(n,m,x\)，询问有多少个长度为 \(n\) 的非负整数序列满足以下条件：
- \(0\le a_1\le a_2\le\dots\le a_n\le m\)
- \(a_1\oplus a_2\oplus\dots\oplus a_n=x\)
答案对 \(998244353\) 取模。
\(1\le n\le200,0\le m<2^{30},\le x<2^{30}\)。
题解
看到 \(m,x\) 的范围，大概是数位 \(\text{dp}\)。但“有序可重“的条件难以处理，我们将答案转化为有序不可重，再转化为无序不可重。
设无序不可重时长度为 \(i\) 的答案为 \(g_i\)，则 \(ans=\sum\limits_{i=1}^n \frac{g_i}{i!}\binom{m+\frac{n-i}{2}}{m}[2|n-i]\)。接下来考虑算出 \(g\)。
注意到无序可重很好求，设 \(f_i\) 为无序可重时长度为 \(i\) 的答案。现在只需通过 \(f\) 得出 \(g\) 即可。也就是去除所有有重复的序列。
对三元组 \((i,j,k)\) 计数，其表示有 \(j\) 个出现奇数次的数，\(k\) 个出现偶数次的数，且这 \(j\) 个数的出现次数之和为 \(i\)。范围 \(i\in[0,n],j\in[0,n),k\in[0,n]\)。
首先选出 \(i\) 个数的位置，方案为 \(\binom{n}{i}\)；再加入奇数，每个奇数可以选 \(i\) 个位置中的任意奇数个，但不能由重叠，方案为 \(\operatorname{odd}(i,j)g_j\)，其中 \(\operatorname{odd}(i,j)\) 表示将 \(i\) 个数放入 \(j\) 个不同集合且每个集合均有奇数个数的方案数。同理放入偶数为 \(\operatorname{even}(n-i,k)(m+1-j)^{\underline{k}}\)。所以：
\[g_n=f_n-\sum_{i=0}^n\sum_{j=0}^{n-1}\sum_{k=0}^n\binom{n}{i}\operatorname{odd}(i,j)g_j\operatorname{even}(n-i,k)(m+1-j)^{\underline{k}} \]其中 \(\operatorname{odd}\) 和 \(\operatorname{even}\) 可以 \(O(n^3)\) 、后面的下降幂可以 \(O(n^2)\) 预处理。再搞个前缀和，对每个 \(n\) 可以 \(O(n^2)\) 求 \(g\)。而前面求 \(f\) 是 \(O(n^2\log m)\) 的。所以总复杂度为 \(O(n(n^2+n^2\log m))=O(n^3\log m)\)。
标签：le,奇数,题解,sum,ABC288Ex,odd,operatorname From： https://www.cnblogs.com/FishJokes/p/17237814.html