시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 169 | 77 | 43 | 41.748% |
The Fibonacci numbers are defined as follows:
The Fibonacci machine operates on an n-element integer register sequence <i1, i2, ..., in> which initially contains zeroes only. The machine provides two operations:
Your task is to write a simulator of the Fibonacci machine.
The first line of the standard input contains two integers n and k (1 ≤ n, k ≤ 100,000), separated by a single space and representing the length of the sequence and the number of operations. Each of the following k lines contains a description of one operation. Such a description consists of a character D or S and two integers a and b (1 ≤ a ≤ b ≤ n), separated by single spaces. The character D stands for adding of 1 to the interval [a, b], and the character S stands for calculating the sum of Fibonacci numbers the sequence numbers of which are from [a, b]. You may assume that at least one operation of type Sappears in the sequence of operations.
For each operation S write to the standard output exactly one line with the desired Fibonacci sum. Each result should be calculated modulo 109 + 7.
5 7 D 1 4 S 1 5 D 3 5 D 2 3 S 1 5 D 2 5 S 2 3
4 6 5
After seven operations the sequence of registers becomes <1, 3, 4, 3, 2>. The result of the last query is equal to F(3) + F(4) = 5.
Contest > Algorithmic Engagements > PA 2009 7-2번