题意：在一个圆上有
个点，现在要以某种方式在其间连边，任意两条边不能相交。
第 个点有权值 ，一条 之间的边权值为 。
一种连边方式的权值定义为所有边的权值和。
求连边方式的期望权值。答案对 取模。
，，时限 。
设 为 个点的环连边不相交的方案数。
设 为 个点的环,已经连边 后连边不相交的方案数。
不难发现，含有 的图和不含
的图之间存在一一对应，则有
。
分别考虑每条边
的贡献，答案为:
连边
后，将整个图划分成了两个子问题，方案数为 和 。
令 ，则：
可以差卷积计算。
问题转化为求出 。考虑递推。
若
号点没有连边，则方案数显然为 。
否则，枚举其第一条边 。
在前面不会有其它与
相连的边，方案数为 。
在后面相当于边上已经连了一条边，方案数为 。
则有 解得 根据
检验，发现取负号符合要求。
问题只剩如何计算 的各项系数。
使用小多项式快速幂即可。
复杂度 。