Description

F(x) = 1 (0 <= x < 4) F(n) = F(n - 1) + F(n - pi) (4 <= x) Pi = 3.1415926535….. 現(xiàn)在給出一個(gè)N，求F(n)。由于結(jié)果巨大，只輸出Mod 10^9 + 7的結(jié)果即可。

Solution

之前在做斐波那契額數(shù)列的第n項(xiàng)的時(shí)候，可以考慮為從0開始，可以選擇+1或+2，一直加到n的方案數(shù)。 那么這道題也大同小異，從0開始可以+1或者+π$/pi$，直到第一次＞n-4的時(shí)候的方案數(shù)（為什么是第一次，因?yàn)閺膎選擇-1或-pi，當(dāng)小于4的時(shí)候就退出1了） 那么在最后到達(dá)n-4的時(shí)候，可能是+1加進(jìn)去的，也可能是+pi加進(jìn)去的，所以要分類討論一下。 如果是+1加進(jìn)去的，那么就要枚舉+pi的次數(shù)，然后求出+1次數(shù)的上限，使得最后加到≤n-4，然后+1就可以突破。然后用組合數(shù)算一算就好了。 如果是+pi加進(jìn)去的，那么和上面類似，只不過是枚舉+1的次數(shù)，然后求+pi的上限而已。

Code