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

　　不会，看不懂。

数学专题测试1

原文：https://www.cnblogs.com/hzoi-cbx/p/12134600.html