hihocoder 1482 출근 기록 II 전달 15 행 a

묘사 하 다.
샤 오 하 이의 알고리즘 수업 선생님 은 수업 때마다 샤 오 하 이의 출근 기록 을 집계 한다.지각 은 L 로 기록 되 고 결석 은 A 로 기록 되 며 제시간에 수업 을 하면 O 로 기록 된다.
한 학기 가 끝나 면 샤 오 하 이의 출근 기록 은 LAO 만 포 함 된 문자열 로 볼 수 있다. 예 를 들 어 'OOOOOOOOOOOLOOOLALLO...' 이다.
샤 오 하 이 가 한 학기 에 한 번 이상 결석 하지 않 고 세 번 연속 지각 하지 않 으 면 샤 오 하 이의 출근 기록 은 합격 이다. 
현재 문자열 의 길이 N, 샤 오 하 이 는 길이 N 의 출근 기록 중 합격 기록 이 모두 몇 가지 인지 알 고 싶 습 니 다. 
예 를 들 어 길이 3 의 합격 출근 기록 은 19 가지 가 있다. OOO OOL OOA OLO OOO LOO AOO OLL OLA OOL LOL LOA AOL LLO LAO LLA LAL ALL 이다.
입력
하나의 정수 N (1 < = N < = 100000).
출력
길 이 는 N 의 합격 기록 총수 이다.결과 가 매우 클 수 있 기 때문에, 당신 은 결과 모델 109 + 7 의 나머지 만 출력 하면 됩 니 다.
샘플 입력

3

샘플 출력

19

이 문 제 는 푸 시 로 풀 수 있다.
g (i) 를 설정 하면 i 의 합격 기록 의 종 수 를 나타 낸다.
f (i) 를 설정 하면 i 로 긴 문자열 에 A 가 없고 합격 기록 이 있 는 종 수 를 표시 합 니 다.
문자열 길 이 를 i 로 설정 합 니 다.
문자열 의 마지막 자리 가 A 라면 방안 수 는 f (i - 1) 가지 방안 이 있 습 니 다.
문자열 의 마지막 두 자리 가 AL 이면 프로젝트 수 는 f (i - 2) 가지 방안 이 있 습 니 다.
문자열 의 마지막 두 자리 가 ALL 이면 방안 수 는 f (i - 3) 가지 방안 이 있 습 니 다.
문자열 의 마지막 자리 가 O 라면 프로젝트 수 는 g (i - 1) 가지 방안 이 있 습 니 다.
(위 에 서 는 AO, AOO 같은 상황 을 고려 하지 않 았 다. 왜냐하면 이 두 가지 정 때문이다.
마지막 이 O 인 경우 에 포함)
마지막 두 분 이 OL 이 라면 g (i - 2) 방안 이 있 고 마지막 두 분 은 OLL 이 며 g (i - 3) 상황 이 있 습 니 다.
그래서 형식 을 얻 었 습 니 다: g (i)  =  f(i-1) + f(i-2) + f(i-3) + g(i-1) + g(i-2) + g(i-3);
마찬가지 로 마지막 이 O, OL, OLL 이라는 세 가지 상황 에 따라 f (i) = f (i - 1) + f (i - 2) + f (i - 3) 를 얻 을 수 있다.
그래서 g (i) = f (i) + g (i - 1) + g (i - 2) + g (i - 3);
초기 상황 은 f0 = 1, f1 = 2, f2 = 4, g0 = 1, g1 = 3, g2 = 8 이다.
f3 = f1 + f2 + f0, (OLL 은 길이 가 3 인 경우 이기 때문에 f0 을 1, 동 리 g0 = 1 로 초기 화 합 니 다)
ac 코드 가 매우 짧 습 니 다. 15 줄 만 있 으 면 됩 니 다.
#include using namespace std; typedef long long ll; const int maxn = 100010,mod = 1000000007; ll f[maxn]={1,2,4,7},g[maxn]={1,3,8,18}; int main(){     for(int i=3;i<=maxn;i++){         f[i] = (f[i-1]+f[i-2]+f[i-3]) % mod;         g[i] = (f[i]+g[i-1]+g[i-2]+g[i-3]) % mod;     }     int n;     cin>>n;     cout<     return 0; }