描述 Description

Hamed has recently found a string t and suddenly became quite fond of it. He spent several days trying to find all occurrences of t in other strings he had. Finally he became tired and started thinking about the following problem. Given a string s how many ways are there to extract k ≥ 1 non-overlapping substrings from it such that each of them contains string t as a substring? More formally, you need to calculate the number of ways to choose two sequences a1, a2, …, ak and b1, b2, …, bk satisfying the following requirements:

k ≥ 1

\[\forall i(1 \leq i \leq k) \ 1 \leq a_i,b_i \leq |s|\]

\[\forall i(1 \leq i \leq k) \ b_i \geq a_i\]

\[\forall i(2 \leq i \leq k) \ a_i > b_{i-1}\]

\[\forall i(1 \leq i \leq k)\] t is a substring of string saisai + 1… sbi (string s is considered as 1-indexed).

As the number of ways can be rather large print it modulo 10⁹ + 7.

描述 Description

Malek has recently found a treasure map. While he was looking for a treasure he found a locked door. There was a string s written on the door consisting of characters ‘(’, ‘)’ and ‘#’. Below there was a manual on how to open the door. After spending a long time Malek managed to decode the manual and found out that the goal is to replace each ‘#’ with one or more ‘)’ characters so that the final string becomes beautiful.

Below there was also written that a string is called beautiful if for each i (1 ≤ i ≤ |s|) there are no more ‘)’ characters than ‘(’ characters among the first i characters of s and also the total number of ‘(’ characters is equal to the total number of ‘)’ characters.

Help Malek open the door by telling him for each ‘#’ character how many ‘)’ characters he must replace it with.

描述 Description

Last week, Hamed learned about a new type of equations in his math class called Modular Equations. Lets define i modulo j as the remainder of division of i by j and denote it by \[i \ mod \ j\]. A Modular Equation, as Hamed’s teacher described, is an equation of the form \[a \ mod \ x =b\] in which a and b are two non-negative integers and x is a variable. We call a positive integer x for which \[a \ mod \ x=b\] a solution of our equation.

Hamed didn’t pay much attention to the class since he was watching a movie. He only managed to understand the definitions of these equations.

Now he wants to write his math exercises but since he has no idea how to do that, he asked you for help. He has told you all he knows about Modular Equations and asked you to write a program which given two numbers a and b determines how many answers the Modular Equation \[a \ mod \ x=b\] has.

描述 Description

Malek lives in an apartment block with 100 floors numbered from 0 to 99. The apartment has an elevator with a digital counter showing the floor that the elevator is currently on. The elevator shows each digit of a number with 7 light sticks by turning them on or off. The picture below shows how the elevator shows each digit.

One day when Malek wanted to go from floor 88 to floor 0 using the elevator he noticed that the counter shows number 89 instead of 88. Then when the elevator started moving the number on the counter changed to 87. After a little thinking Malek came to the conclusion that there is only one explanation for this: One of the sticks of the counter was broken. Later that day Malek was thinking about the broken stick and suddenly he came up with the following problem.

Suppose the digital counter is showing number n. Malek calls an integer x (0 ≤ x ≤ 99) good if it’s possible that the digital counter was supposed to show x but because of some(possibly none) broken sticks it’s showing n instead. Malek wants to know number of good integers for a specific n. So you must write a program that calculates this number. Please note that the counter always shows two digits.

描述 Description

Chef likes trees a lot. Today he has an infinte full binary tree (each node has exactly two childs) with special properties.

Chef’s tree has the following special properties :

Each node of the tree is either colored red or black.

Root of the tree is black intially.

Both childs of a red colored node are black and both childs of a black colored node are red.

The root of the tree is labelled as 1. For a node labelled v, it’s left child is labelled as 2v and it’s right child is labelled as 2v+1.

Chef wants to fulfill Q queries on this tree. Each query belongs to any of the following three types:

Qi Change color of all red colored nodes to black and all black colored nodes to red.

Qb x y Count the number of black colored nodes on the path from node x to node y (both inclusive).

Qr x y Count the number of red colored nodes on the path from node x to node y (both inclusive).

Help chef accomplishing this task.