题意：有
颗珠子，每个珠子的颜色在
中等概率随机，求能找出
个同色对子的概率。
答案对 取模，，，时限 。
求出符合要求的方案数，再除以总方案数 即可。
出现偶数次的颜色均可配对，出现奇数次的颜色有一个无法配对。由于最多浪费
个珠子，出现奇数次的颜色不超过
个（这是充要条件）。
算法一：卷积
记 为钦定 个颜色出现偶数次的方案数， 为恰好
个颜色出现偶数次的方案数，根据组合意义和二项式反演
若得到 ，可以用卷积加速二项式反演 求出 ，答案即为 。
出现任意次的颜色的数列为 ，EGF 为 。
出现偶数次的颜色的数列为 ，EGF 为 。
易知 忽略常数 显然是卷积的形式，可以 计算。
算法二：整式递推
考虑二元生成函数，
表示出现次数，
表示出现次数为奇数的颜色数。单个颜色的 EGF 为 共有
种颜色，则颜色序列（排成一排的
个珠子）的 EGF 为 。
约束是奇数不超过
个。答案即为 把 代换掉，令 我们需要 。
为了避免负次数，可以改为 则只需 。
若已知
的各项系数，答案易求。具体而言 线性筛幂即可做到 。
接下来思考如何线性求
的系数。
记 ，则
。
满足不齐次微分方程 易知
也满足某种不齐次微分方程。
抹去尾项，设
满足齐次微分方程 ，解得 ，令 ，先推导出
的齐次微分方程，加上一个尾项就能得到
的微分方程，而这个尾项必然是代数的。
计算得 ，易知其满足齐次微分方程
。那么 满足微分方程 其中尾项
为（代数的）某多项式。
用待定系数法求出
的整式递推， 求出 ，然后对 提取 系数得 ，即可求出 。（ 需要特殊处理）
注：事实上，如果进行精确计算，可知 。
欲求 ，则我们需要解决
的
ODE，求导可得
总复杂度 。