Skip to content

1455: 小V的和弦

题目

题目描述

作为一名爱好音乐的业余小提琴手,小V经常在空闲的时候来研究和弦的构成。(小J:我也不知道小提琴咋整出不拆分的和弦(逃~))

小V把一个和弦定义为n个音符组成的序列,每个音符都有一个频率值。

经过长时间的研究,小V发现,当一个和弦里的第i个音符的频率值小于第i+2(如果存在)和第i+3(如果存在)个音符的频率值时,这个音乐会更加的每妙。

为了便于分析,小V假定,对于一个n个音符组成的和弦,每个音符的频率值都是一个属于[1,n]的正整数。

现在小V想知道,对于一个给定的正整数n,共有多少种不同的和弦呢。

注意两个和弦不同,当且仅当存在一个位置,这两个和弦此位置上的音符频率值不相同。

输入格式

一个正整数n

输出格式

一行一个数,表示不同和弦的种类数。结果对4294967296取模。

样例输入

3

样例输出

9

数据范围

对于20%的数据,1 <= n <= 50

对于50%的数据,1 <= n <= 300

对于100%的数据,1 <= n <= 1000

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!