A. 解方程

　　容易发现第二个限制挺没用的，直接减去就行。

　　对于第一个限制，发现没办法直接做，考虑容斥。设$f_s$表示$s$集合中的数不满足限制的方案数，随便容斥一下：

　　$$ans=\sum\limits-1^{|s|}*f_s$$

　　可以发现，实际上$f_s$就是一个组合数，可以用挡板法得到，发现模数不保证为质数，exLucas直接算即可。

B. 宇宙序列

　　容易发现，题中所给的式子就是一个异或卷积，我没发现，所以：$a_i=a_{i-1}*a_1$。

　　而异或卷积是满足结合率的，所以：$a_{2*i}=a_i*a_i$。

　　然后直接倍增求这个东西，用fwt优化就可以做到$O(2^n*n*p)$。

　　然后由于异或卷积有一些优美的性质，所以可以将对应位置点值相加，最后统一IDFT回去也是正确的。

　　于是原问题转化成了这样：给定一些数$x$，对于每个$x$，求出$\sum\limits_{i=0}^{p}x^{2^{i}}$。

　　这题模数非常小，底数只有10007种，可以考虑暴力预处理。

　　考虑倍增，令$f_{x,i}=\sum\limits_{j=0}^{2^{i}-1}x^{2^{j}}$，有转移：

　　$$f_{x,i}=f_{x,i-1}+f_{x^{2^{2^{i-1}}},i-1}$$

　　所以暴力对所有$x$预处理出来倍增数组，对于DFT之后的$a_1$进行倍增求出和然后IDFT回去即可。

　　加优化可以做到$O(n*2^n+mod*logmod)$。

C. exp

　　又是神仙期望dp。。

　　首先根据传统，断环成链。考虑整个序列，最后一个变为X的贡献一定是$\frac {n-1}{2}$，于是就转化为了序列上的问题。

　　对于区间$[l,r]$，如果中间存在一个点$k$为'.'，那么区间$[l,k]$，$[k+1,r]$是互不干涉的，于是可以考虑转移。

　　设$g_{l,r}$表示区间$[l,r]$除了r都已经被变为X，且r为'.'的概率，$f_{l,r}$表示期望，注意此处的期望实际上是总和，并未乘概率。$p(l,r,k)$表示区间$[l,r]$除了r最后一个变为X的位置是$k$，且$r$为'.'的概率，$lc$为$[l,k]$中'.'的个数，$rc$为$[k+1,r]$中'.'的个数。那么有：

　　$$p(l,r,k)=C_{lc+rc-2}^{lc-1}(\frac{k-l+1}{r-l+1})^{lc}(\frac{r-k}{r-l+1})^{rc-1}*p_{l,k}*p_{k+1,r}$$

　　实际上就是将两个区间合并起来，并且用方案总数乘以合法概率。

　　那么：

　　$$g_{l,r}=\sum\limits_{i=l}^{r-1}p(l,r,k)$$

　　$$f_{l,r}=\frac{1}{g_{l,r}}\sum\limits_{i=l}^{r-1}p(l,r,i)(f_{l,i}+f_{i+1,r}+\frac{k-i}{2})$$

　　实际上就是对于所有部分的期望做了加权平均。

　　统计答案只要枚举最后一个端点r，累加贡献：$ans=\sum\limits_{i=1}^{n}f_{i,i+n-1}*g_{i,i+n-1}$

　　最后加上最后一步的贡献，即$\frac{n-1}{2}$。