Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.*;
- import java.util.StringTokenizer;
- public class FibonacciMachine {
- static class Solver {
- final int[][] A = new int[][]{{1, 1}, {1, 0}};
- final int[][] I = new int[][]{{1, 0}, {0, 1}};
- final int[][] F1_F0 = new int[][]{{1}, {0}};
- final int[][] ZERO = new int[][]{{0}, {0}};
- final int MOD = (int) 1e9 + 7;
- int n, q;
- int[][][] tree;
- int[] lazy;
- // -----------------------------------
- int add(int a, int b) {
- return ((a % MOD) + (b % MOD)) % MOD;
- }
- int mul(int a, int b) {
- return (int) (((long) (a % MOD) * (b % MOD)) % MOD);
- }
- int[][] mul(int[][] a, int[][] b) {
- int[][] result = new int[a.length][b[0].length];
- for (int i = 0; i < a.length; i++) {
- for (int j = 0; j < b[0].length; j++) {
- for (int k = 0; k < b.length; k++) {
- result[i][j] = add(result[i][j], mul(a[i][k], b[k][j]));
- }
- }
- }
- return result;
- }
- int[][] pow(int[][] a, int n) {
- if (n == 0) {
- return I;
- } else if (n % 2 == 0) {
- return pow(mul(a, a), n >> 1);
- } else {
- return mul(a, pow(mul(a, a), n >> 1));
- }
- }
- // -----------------------------------
- void push(int n, int l, int r) {
- if (lazy[n] != 0) {
- tree[n] = mul(pow(A, lazy[n]), tree[n]);
- if (l != r) {
- lazy[n + n] += lazy[n];
- lazy[n + n + 1] += lazy[n];
- }
- lazy[n] = 0;
- }
- }
- int[][] combine(int[][] a, int[][] b) {
- return new int[][]{{a[0][0] + b[0][0]}, {a[1][0] + b[1][0]}};
- }
- void build(int n, int l, int r) {
- if (l == r) {
- tree[n] = F1_F0;
- } else {
- int m = (l + r) >> 1;
- build(n + n, l, m);
- build(n + n + 1, m + 1, r);
- tree[n] = combine(tree[n + n], tree[n + n + 1]);
- }
- }
- int[][] query(int n, int l, int r, int s, int e) {
- push(n, l, r);
- if (l > e || r < s) {
- return ZERO;
- } else if (s <= l && r <= e) {
- return tree[n];
- } else {
- int m = (l + r) >> 1;
- return combine(
- query(n + n, l, m, s, e),
- query(n + n + 1, m + 1, r, s, e)
- );
- }
- }
- void update(int n, int l, int r, int s, int e) {
- push(n, l, r);
- if (l > e || r < s) {
- } else if (s <= l && r <= e) {
- tree[n] = mul(A, tree[n]);
- if (l != r) {
- lazy[n + n]++;
- lazy[n + n + 1]++;
- }
- } else {
- int m = (l + r) >> 1;
- update(n + n, l, m, s, e);
- update(n + n + 1, m + 1, r, s, e);
- tree[n] = combine(tree[n + n], tree[n + n + 1]);
- }
- }
- // -----------------------------------
- void solve() throws Exception {
- n = nextInt();
- q = nextInt();
- tree = new int[4 * n + 5][2][1];
- lazy = new int[4 * n + 5];
- build(1, 1, n);
- while (q-- > 0) {
- if (next().equals("D")) {
- update(1, 1, n, nextInt(), nextInt());
- } else {
- writer.println(query(1, 1, n, nextInt(), nextInt())[1][0]);
- }
- }
- }
- }
- // -------------------------------------
- static BufferedReader reader;
- static StringTokenizer tokenizer;
- static PrintWriter writer;
- static String next() throws Exception {
- while (tokenizer == null || !tokenizer.hasMoreTokens()) {
- tokenizer = new StringTokenizer(reader.readLine());
- }
- return tokenizer.nextToken();
- }
- static int nextInt() throws Exception {
- return Integer.parseInt(next());
- }
- public static void main(String[] args) throws Exception {
- reader = new BufferedReader(new InputStreamReader(System.in));
- reader = new BufferedReader(new InputStreamReader(new FileInputStream("_in")));
- writer = new PrintWriter(System.out);
- writer = new PrintWriter(new File("_out"));
- Solver solver = new Solver();
- solver.solve();
- reader.close();
- writer.close();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement