多边形是由至少三条直线段首尾相接形成的封闭平面图形。各直线段不能自交，相邻两段也不能共线。

若多边形的各边长度均为整数且均不相等，则将这些长度组成的整数集称为多边形的生成集。

例如$\{3, 4, 5\}, \{6, 9, 11, 24\}$都是多边形的生成集，但$\{1, 2, 3\}$和$\{2, 3, 4, 9\}$都不是多边形的生成集。

考虑初值为$s_1=1, s_2=2, s_3=3$，且满足递推式 $$s_n=s_{n-1}+s_{n-3},$$。的序列，并记$U_n=\{s_1, s_2, \ldots, s_n\}$。例如$U_{10}=\{1, 2, 3, 4, 6, 9, 13, 19, 28, 41\}$。

记$f(n)$为$U_n$中能作为多边形生成集的子集总数，例如$f(5)=7, f(10)=501, f(25)=18635853$。

求$f(10^{18})$的最后九位数字。

本题难度:

解答

与三角形的情况类似，一组数形成多边形的充要条件是最大数小于其他所有数之和。

本题可以通过是否包含最后一个数在生成集中作动态规划来求出$f(n)$的以下递推式，也可以暴力枚举较小的n来解出系数: $$f(n)=4f(n-1)-5f(n-2)+4f(n-3)-7f(n-4)+6f(n-5)+2f(n-7)-5f(n-8)+2f(n-9).$$ 将其写作矩阵形式再作快速幂即得结果$697003956$。

注：为减少码量，以下用numpy来作矩阵快速幂，因此代码为Python 3。

import numpy as np

n=10**18
m=10**9
a=np.zeros((9,9),dtype=np.int64)
a[0]=[4,-5,4,-7,6,0,2,-5,2]

for i in range(1,9):
    a[i][i-1]=1

r=np.identity(9,dtype=np.int64)
print(r)
k=n-1
while k>0:
    if k & 1:
        r=np.dot(a,r)%m
    k//=2
    a=np.dot(a,a)%m

print(np.dot(r[-1],np.array([236,108,47,19,7,2,0,0,0]))%m)