약한 파이thhonista라서 AtCoder에 한 번도 참가한 적이 없어요.
싸울 시간이 얼마 남지 않았다는 생각에 의욕을 북돋우고 AtCoder에 전념해 보았다.
A, B 문제는 간단하지만 상관없다
제가 봤을 때 C 문제는 어려워요.
그래서 우리는 AtCoder 129의 C 문제를 해결해 보았다.

AtCoder129의 C 문제

그렇구나, 정말 재미있다.

내 머릿속에는 수 A 범위의 가장 짧은 경로 문제가 떠올랐다

이런 녀석, 잘 풀었지.
P지점을 통해 A에서 B까지의 최단 노선은 몇 가지가 있는데 이 문제입니다.
A에서 P까지의 탈법 총수와 P에서 B까지의 탈법 총수를 계산하려면 계산이 필요하다.
그립다~
ABC 문제로 돌아가겠습니다.
부서진 마루 사이의 마루에 각각 몇 가지 이동 방법을 요구한다
그걸 같이 걸면 돼.
간단해!그렇게 생각하지만.

이동법은 몇 가지??

정신을 차리다.
내 인생은 항상 순조롭게 일희일우하며 반복되고 있다.
따라서 바닥의 개수가 1의 경우,2의 경우,,,머리에서 계산하면
계속된 바닥 개수
이동할 수 있는 수량
1
1
2
2
3
3
4
5
5
8
:
:

피보나치 선생님!!

피보나치 수열을 말하자면
F0 = 0,
F1 = 1,
Fn + 2 = Fn + Fn + 1 (n ≧ 0)
모두가 가장 좋아하는 이 점화식.
자연계 곳곳에서 볼 수 있다
유명한 해바라기 씨앗의 개수, 앵무새의 나선 구조
황금 비율도 이 멋진 수학 세계에 도달할 수 있다.
그래서 답은 이미 머릿속에서 완성됐다.
그리고 코드만 쓰면 돼요.
ABC.py

#配列内の全ての数値の積を求める際に必要
from operator import mul
from functools import reduce

# リスト内包表記で入力を変数やリストに代入
n, m = [int(i) for i in input().split()]
arr = [int(input()) for i in range(m)]

#始点（0）と終点（n）をarrに追加するが、壊れた床間の差分をとる際にずれるので、視点は-1,終点は+1しておく
arr.append(n+1)
arr.insert(0, -1)
#壊れた床同士間にある床の数をリストに内包
div_arr = [arr[i+1]-arr[i]-1 for i in range(len(arr)-1)]

#フィボナッチ数列を定義
def Fib(n):
    a, b = 0, 1
    if n == 1:
        return a
    elif n == 2:
        return b
    else:
        for i in range(n-2):
            a, b = b, a + b
        return b

#div_arr内の全ての数をフィボナッチ数列の関数に入れ、それらを全て掛け合わせる
print(reduce(mul, [Fib(i+1) for i in div_arr])%1000000007)

이상은 ABC 문제의 나만의 해법이다.