因为没做过数学题。
所以打算先随便找+做几个简单数学题，再写题解，过段时间再讲。
另：由于我之前讲的数学题难度太大，被多人联名怒喷，广受差评，所以这次的难度大大降低，题太水。
做过的大佬不要大声喷或喊题解，没做过的神秒切不要说题真太水。
本来计划弄10个题，由于本人水平有限，这段时间内过于颓废，所以只做了8个题。
(T1)
(CF438E The Child and Binary Tree)
有一个大小为(n)的集合(S)问所有点权都在集合中，并且点权之和分别为([1,m])的二叉树的个数。
(n,m<=10^5)
设(f(i))为权值和(i)的二叉树个数，(c(i))为权值集合中是否存在(i)。
那么有：
[f(n)=sumlimits_{i=1}^{m}c(i)sumlimits_{j=0}^{n-i}f(j)f(n-i-j)
]
由于(f(0)=1)
设({f},{c})生成函数分别是(F(x),C(x))
所以：
[F(x)=F(x)F(x)C(x)+1
]
解得：
[F(x)=frac{2}{1(+/-)sqrt{1-4C(x)}}
]
然后考虑符号变化。
当(limlimits_{x
ightarrow 0})的时候，(F(x)
ightarrow f(0))
那么当符号是正好的时候才存在这个结果，所以舍去负号。
那么我们做一个多项式开根和求逆就好了。
(T2)
UOJ#62 [UR #5] 怎样跑得更快
(nqleq 10^5)
其实这个题就是猛推式子。
[egin{aligned}
b_i&equiv sumlimits_{j=1}^{n}(i,j)^c[i,j]^ex_j\
&equiv sumlimits_{j=1}^{n}(i,j)^{c-e}i^ej^ex_j\
&equiv i^esumlimits_{d|i}d^{c-e}sumlimits_{d|j}j^ex_j[frac{(i,j)}{d}=1]\
&equiv i^esumlimits_{d|i}d^{c-e}sumlimits_{d|j}j^ex_jsumlimits_{g|frac{(i,j)}{d}}mu(g)\
&equiv i^esumlimits_{d|i}d^{c-e}sumlimits_{d|j}j^ex_jsumlimits_{T|(i,j)}mu(frac{T}{d})\
&equiv i^esumlimits_{T|i}sumlimits_{T|j}j^ex_jsumlimits_{d|T}mu(frac{T}{d})d^{c-e}\
&equiv i^esumlimits_{T|i}sumlimits_{T|j}j^ex_jf(T)\
&equiv i^esumlimits_{T|i}f(T)g(T)\
&equiv i^esumlimits_{T|i}F(T)\
frac{b_i}{i^e}&equiv sumlimits_{T|i}F(T)\
F(n)&equiv sumlimits_{n|i}mu(frac{i}{n})frac{b_i}{i^e}
end{aligned}
]
这就完事了。
一个反演解决了。
(T3)
UOJ#310. 【UNR #2】黎明前的巧克力
(nleq 10^6,a_ileq 10^6)
这个题可以直接转化题意。
变成对于一个可重集合(S)，选择其(xor)和为(0)的子集(T)，那么这个子集对答案的贡献就是(2^{|T|})。
那么我们可以搞一个集合幂级数二项式来当生成函数用。
那么每个元素的生成函数就是((1+2x^{a_i}))。
每个都(FWT)一次复杂度太高了。
考虑(FWT)的式子。
设(i)的二进制位上(1)的个数为(d(i))。
那么有：
[c_i=sumlimits_{j}(-1)^{d(i&j)}b_j
]
那对于系数来说，1的贡献是1，2的贡献是((+/-)2)这怎么弄呢,那么一个多项式的贡献不是(-1)就是(3)？
考虑把这些多项式求和再(FWT)。
这样每个位置得到的答案就是:
[(-1)x+3(n-x)=f_i
]
这样可以解出来每个位置的(-1)的个数。
真实的系数就是:
[c_i=(-1)^x3^{n-x}
]
我们再给他(IFWT)回去就行。
注意去掉空集的方案。
(T4)
(THUPC2017 findtree)
事实上我们要求的就是每一种权值的方案数是否为0.
怎么做？
首先我们发现不能拆位来做。
就很恶心。
否则可以直接做矩阵树定理来求这个东西。
我们其实仍然可以拆位来做。
用(exFWT)来把每一位拆成点值。
然后直接用变元矩阵树定理处理这个桶，求出每一个位置应当有的权值。
这相当于对所有的点值做一个树形乘法。
正好符合点值对位相乘的性质。
得到的新桶我们在(exIFWT)回来就得到了最终的方案数数组。
(exFWT)的用法是在每一位可以用不同的位运算来计算。
只需要在不同的位用不同的(FWT)计算方法就可以。
正确性显然。
(T5)
(NOI2016)循环之美
这个题作为(NOI)的题目总体还算中规中矩。
话说(NOI)的题目，结论题几乎都有提示欸。
这个提示的意思大概就是说在做除法的时候存在这样的事情：
[xK^lequiv x(mod y)
]
就是说余数在(l)次后重新出现。
那么有:
[K^lequiv 1(mod y)
]
根据欧拉定理来说，有(varphi(y)|l,(K,y)=1).
同时由于是数值上互不相等，那么可以认为(frac{x}{y})为最简分数形式。
那么可以大胆地列出最终答案的表达式:
[ans=sumlimits_{i=1}^{n}sumlimits_{j=1}^{m}[(i,j)=1][(j,K)=1]
]
剩下就是无聊的推式子环节了,不过也有几步惊心动魄的操作地说：
[egin{aligned}
ans&=sumlimits_{i=1}^{n}sumlimits_{j=1}^{m}[(i,j)=1][(j,K)=1]\
&=sumlimits_{j=1}^{m}[(j,K)=1]sumlimits_{i=1}^{n}[(i,j)=1]\
&=sumlimits_{j=1}^{m}[(j,K)=1]sumlimits_{i=1}^{n}sumlimits_{d|(i,j)}mu(d)\
&=sumlimits_{d=1}^{min(n,m)}[(d,K)=1]mu(d)lfloorfrac{n}{d}
floorsumlimits_{j=1}^{lfloorfrac{m}{d}
floor}[(jd,K)=1]\
f(n,K)&=sumlimits_{d=1}^{n}[(d,K)=1]mu(d)\
&=sumlimits_{d=1}^{n}mu(d)sumlimits_{g|(d,K)}mu(g)\
&=sumlimits_{g|K}mu(g)sumlimits_{d=1}^{lfloorfrac{n}{d}
floor}mu(d)\
&=sumlimits_{g|K}mu^2(g)sumlimits_{d=1}^{lfloorfrac{n}{g}
floor}mu(d)[(d,g)=1]\
&=sumlimits_{g|K}mu^2(g)f(lfloorfrac{n}{g}
floor,g)\
g(n)&=sumlimits_{i=1}^{n}[(i,K)=1]\
&=lfloorfrac{n}{K}
floor g(K)+g(K-lfloorfrac{n}{K}
floor K)\
end{aligned}
]
这样一边预处理快速查询，一边直接杜教筛就行了。
(T6)
([Luogu3768])简单的数学题
这个题用到一些欧拉函数的套路。
推一波式子就出来了：
[egin{aligned}
ans&=sumlimits_{i=1}^{n}sumlimits_{j=1}^{n}ij(i,j)\
&=sumlimits_{d=1}^{n}d^3sumlimits_{i=1}^{lfloorfrac{n}{d}
floor}sumlimits_{j=1}^{lfloorfrac{n}{d}
floor}ij[(i,j)=1]\
&=sumlimits_{d=1}^{n}d^3sumlimits_{i=1}^{lfloorfrac{n}{d}
floor}sumlimits_{j=1}^{lfloorfrac{n}{d}
floor}ijsumlimits_{g|(i,j)}mu(g)\
&=sumlimits_{d=1}^{n}d^3sumlimits_{g=1}^{lfloorfrac{n}{d}
floor}mu(g)g^2sum^2(lfloorfrac{n}{dg}
floor)\
&=sumlimits_{T=1}^{n}sum^2(lfloorfrac{n}{T}
floor)sumlimits_{d|T}d^3(frac{T}{d})^2mu(frac{T}{d})\
&=sumlimits_{T=1}^{n}sum^2(lfloorfrac{n}{T}
floor)T^2sumlimits_{d|T}dmu(frac{T}{d})\
&=sumlimits_{T=1}^{n}sum^2(lfloorfrac{n}{T}
floor)T^2varphi(T)\
f(n)&=n^2varphi(n)\
S(n)&=sumlimits_{i=1}^{n}f(i)\
g(n)&=n^2\
h(n)&=n^3\
f*g&=h\
S(n)&=sumlimits_{i=1}^{n}i^3-sumlimits_{d=2}^{n}d^2S(lfloorfrac{n}{d}
floor)\
end{aligned}
]
这就完事了。
(T7)
堪破神机
考虑(m=2)的时候，设方案数为(f_i)那么其实({f})就是斐波那契数列。
这样我们求一下这个数列的特征根。
[x^2=x+1
]
这样有:
[alpha=frac{1+sqrt{5}}{2},eta=frac{1-sqrt{5}}{2}
]
我们知道特征根可以用于表示线性递推数列。
[f_n=Aalpha^n+Beta^n
]
代入前几项解得：
[f_n=frac{1}{sqrt{5}}alpha^n-frac{1}{sqrt{5}}eta^n
]
那么有:
[egin{aligned}
ans&=sumlimits_{i=L}^{R}inom{f_i}{K}\
&=frac{sumlimits_{i=L}^{R}f_i^{underline{K}}}{K!}\
&=frac{1}{K!}sumlimits_{i=L}^{R}sumlimits_{k=0}^{K}(-1)^{K-i}egin{bmatrix}K\iend{bmatrix}f_i^k\
&=frac{1}{K!}sumlimits_{k=0}^{K}(-1)^{K-i}egin{bmatrix}K\iend{bmatrix}sumlimits_{i=L}^{R}f_i^k\
&=frac{1}{K}sumlimits_{k=0}^{K}(-1)^{K-i}egin{bmatrix}K\iend{bmatrix}sumlimits_{i=L}^{R}(Aalpha^i-Beta^i)^k\
&=frac{1}{K}sumlimits_{k=0}^{K}(-1)^{K-i}egin{bmatrix}K\iend{bmatrix}sumlimits_{i=L}^{R}sumlimits_{j=0}^{k}inom{k}{j}(Aalpha^i)^j(Beta^i)^{k-j}\
&=frac{1}{K}sumlimits_{k=0}^{K}(-1)^{K-i}egin{bmatrix}K\iend{bmatrix}sumlimits_{j=0}^{k}inom{k}{j}A^jB^{k-j}sumlimits_{i=L}^{R}alpha^{ij}eta^{i(k-j)}\
end{aligned}
]
那我们搞个扩域就行了。
直接设个(i=sqrt{5})
然后做一些复数运算最终就可以求到答案了。
上面那个式子的话后面的部分由于可以直接搞等比数列求和。
所以复杂就是(O(K^2logn))的。
再来考虑(m=3)的情况。
设方案为(g_i)。
那么有：
这样的话数列的式子呼之欲出了。
[g_i=g_{i-1}+2sumlimits_{j=0}^{i-1}g_{j}
]
然后错位相减一下。
[g_{i}-g_{i-1}=g_{i-1}+2sumlimits_{j=0}^{i-1}g_j-g_{i-2}-2sumlimits_{j=0}^{i-2}g_j=3g_{i-1}-g_{i-2}
]
所以:
[g_i=4g_{i-1}-g_{i-2}
]
同样可以搞个特征方程出来。
[x^2=4x-1
]
那么解得:
[alpha=frac{4+sqrt{8}}{2}=2+sqrt{3},eta=2-sqrt{3}
]
仍然可以求出(A,B)，略。
这样我们其实直接代入(i=sqrt{3})就可以了。
仍然可以用上面的方法再做一次。
这个题，出题人强行多合一。
(T8)
这个应该是那个斯特林反演的题，貌似是叫异或图来着，久闻大名了。
首先枚举一些划分情况(A)，表示将集合中的点划分为多个子集，每个子集大小为(a_i),总共有(|A|)个子集。
设(g_A)为将点集划分成(A)的情况，不同集合必然没有连边，相同集合可能有所连边的方案，(f_A)为恰好把点集分成(A)的方案。
这样可以用斯特林反演容斥出来(f)，问题转化为求(g)。
求(g)是这个题的难点。
那么也就是说对于每条确定了的边都可以列出一个(xor)方程。
这样其实维护一下线性基的大小就可以了，设这个大小为(k)，那就是确定了(k)个图的了，那么总的符合这种情况的子集个数就是(2^{m-k})。
把(A)按照(|A|)搞个占位多项式。
这样我们最后玩个斯特林反演就可以了：
[g_m=sumlimits_{i=m}^{n}egin{Bmatrix}i\mend{Bmatrix}f_i
]
[f_m=sumlimits_{i=m}^{n}(-1)^{i-m}egin{bmatrix}i\mend{bmatrix}g_i
]
求个(g_1)就完事了。