#P4228. Tibbar的后花园

    ID: 3446 传统题 2000ms 512MiB 尝试: 114 已通过: 7 难度: 8 上传者: 标签>CF2500省选/NOI-无向连通分量指数生成函数导数积分转化线性递推滚动数组

Tibbar的后花园

题目描述

在 nn 个互不相同的标号点之间选择一些无向边,得到一张简单无向图。任意两个点至多连一条边,一个点不能和自身连边。

两点的距离是连接它们的最短路包含的边数。三个不同的点在同一个连通分量内,且它们之间的三对距离全部相等时,称它们为一组违规三点。跨连通分量的点对不可达,不能构成违规三点。

求没有违规三点的连边方案数。

输入格式

输入一个整数 nn(1≤n<2201\le n<2^{20})。

输出格式

输出一个整数,表示方案数对 10045358091004535809 取模后的值。

样例

3
7

三个标号点之间的三条可能边共有八种选法。只有三角形包含一组两两距离均为 11 的点,因此有七种合法方案。

原题及公开评测数据