382. Generating polygons http://projecteuler.net/problem=382 一个多边形是为由线段连接成封闭环的平面图形，至少包含三段直线且不自身相交。 （译注: 就是平常说的「简单多边形」） 一个仅含正数的集合 S 说它「产生多边形 P」如果： * P 没有两边长度相同， * P 的所有边长都在 S 中， * S 不包含其他不是 P 边长的值。 例如： * 集合 {3,4,5} 产生一个三边长分别为 3,4,5 的多边形 (这里是三角形)； * 集合 {6,9,11,24} 产生一个四边长分别为 6,9,11,24 的多边形 (这里是四边形)； * 集合 {1,2,3} 和集合 {2,3,4,9} 并不产生任何多边形。 考虑数列 S 由以下定义： * S_1 = 1, S_2 = 2, S_3 = 3 * S_n = S_{n-1} + S_{n-3} 再令 U_n 为集合 {S_1, S_2, ..., 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) 的末九位数。 -- S 这个数列在很多地方都有出现就不赘述了 (OEIS A930，可自行查阅) 比较大的问题是判断多边形... -- ◢ ˊ_▂▃▄▂_ˋ. ◣　　　　　 　　　　▅▅　▅▅　ι●╮　　 █▄▄▄▄▄ ▍./◤_▂▃▄▂_◥ \'▊ 　　ＨＡＲＵＨＩ █████　＜■┘ 　 ▄▄▄▄▄▄▄ ▎⊿ ◤◤◥█◥◥█Δ 　　ＩＳＭ　 　　By-gamejye　￠|\ 　　▌▌▌▌▌▄▌▌ ▏ζ(▏●‵◥′●▊)Ψ ▏　　 　　　 　　　　█　　　 ⊿Δ 　　▄▄▄ ▄▄▄▄ █/|▊ 〃 、 〃▋ |\ ▎　　　　　 　 　ハルヒ主义　　　 　　█▄▄▄█▄▄ ◥◥|◣ ‵′ ◢/'◢◢S.O.S 世界を大いに盛り上げるための凉宫ハルヒの団　　　 --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 140.112.28.91