| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 12219 | Uncle Huang Points Tutor |
|
| 12241 | Restaurants in Hsinchu |
|
| 12371 | Crazy give head |
|
Description
Disclaimer: If something described below happened or happens in real world, which is just a coincidence. We will not take any responsibility of any coincidence.
Uncle: I'm an employee of the library and dating master, nickname "Uncle Huang", who are you?
Shiao: Two years tutor experience, straying book boy of second-hand section, "Shiao Tsing".
Uncle: Well, well. Let me test you!
Uncle: In the painting, dragons won't roar, tigers won't howl, little book boy, funny funny!
Shiao: In the article, man is allowed, woman is forbidden, seeking tutor, urgent urgent!
Uncle: Warbler, swallow, emerald, red, prosperous, harmonious, everywhere.
Shiao: Tutor, Shu-shu, urgent, critial, anxious, serious, swimming pool.
Wang Ye: Another distich!
Uncle: See a jerk standing over there.
Shiao: Seek a tutor swimming over the pool.
Uncle: I am hero in the battle field.
Shiao: You are topic master booming the post.
Uncle: Ahhhhh........!
(Inspired by the post 靠北清大7754)
Although uncle Huang loses the distich competition, he is still seeking for a male tutor. He would choose one of those who left comments below his post as his tutor ( and one cannot refuse! ). Because too many people left comments below ( just like Shiao said, he's truly a topic master ), he would pick two numbers "x" and "y", and choose the (xy)-th person that left a comment as his tutor.
Because xy might be too big, so the answer would mod(取模) a number "m", which is the total number of comments of his post.
Uncle Huang is too busy seeking for his true love tutor, he asks you for help, could you help him find out his true love tutor?
- You are given three numbers "x", "y", and "m", you have to calculate the answer of ((xy)%m) .
Hint: Use "Fast Power" method to solve this problem!
Input
The input contains only one line.
The first line contains exactly three numbers "x", "y", and "m", which are described above.
1 <= x <= 1018,, 0 <= y <= 1018, 1 <= m <= 109.
Output
Output one number: (xy)%m .
Remember th print a '\n' at the end of the output.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
After some hard work of finding his queen, Knuckles finally arrived NTHU!
Knuckles is exhausted. He wants to grab some delicious food. However, as all of us know......
THERE IS NO "DELICIOUS" FOOD IN HSINCHU.
(Actually there are some restaurants that are not bad. But just "not bad"...)
This truth, which is cruel, hits Knuckles pretty hard. Knuckles doesn't give up and start his journey of finding delicious food in Hsinchu.
However, the more he goes out and seeks, the truth is just getting more clear...
The i-th time that those bad-taste restaurants Knuckles found is Fi . Knuckles found that F1 = 1, F2 = 1, and Fi = Fi-1 + Fi-2 .
The more Knuckles goes out, the more bad-taste restaurants he found.
He is tired of finding more and more bad restaurants. He just wants to know there are how many bad restaurants when he goes out for the i-th time.
- There's a sequence F.
- F1 = 1, F2 = 1, Fi = Fi-1 + Fi-2.
- Find out Fi .
Hint：
Input
The input contains multiple lines, ended by EOF.
Every line contains an integer i.
1 <= i <= 1018.
There will be at most 20 lines.
Output
Output Fi.
Because Fi might be too big, the answer should mod 109+7, which means you should output Fi % (109+7).
Remember to print a '\n' at the end of the output.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
A famous streamer once said: "From now on, CRAZY GIVE HEAD!!". The streamer was so furious that he said many dirty words. You wonder how many times did a specific word appears in those words.
You will have one long string S and one short string p.
Then you will have q times of queries.
Each query includes two numbers a, b which indicate the range in string S.
The sum of a range indicates the occurrences of string p from position a of string S to position b of string S.
Your task is finding the maximum sum from all the queries.
Note that the index is start from 1.
For example:
You have S="ababaaaaba" and p="ba". You got q = 5, the five queries are as follow:
8 9
2 5
6 7
6 6
2 4
Position 8 to position 9 the occurrence of p equals 0
Position 2 to position 5 the occurrence of p equals 2
Position 6 to position 7 the occurrence of p equals 0
Position 6 to position 6 the occurrence of p equals 0
Position 2 to position 4 the occurrence of p equals 1
Therefore, the answer is 2.
Hint: The biggest problem is that if you construct a prefix sum array based on the occurrences of p[0] and check if it makes the entire p , you will get error when the range cut the "part of p".
Therefore consider this: if we want to avoid the "part of p" problem we can consider that if a part of p will be cut in range (L, R) that means p[0] must in the place of (R-length(p)+2, R). Therefore we only need to consider range (L,R-length(p)+1)
To sum up, we can change the range (L, R) into (L, R-length(p)+1). Use the prefix sum array to calculate this problem will be like: prefix[ R-length(p)+1 ] - prefix[ L-1 ]. In this way, we can avoid the "part of p" problem and solve the question.
⠄⠄⠄⠄⠄⠄⠄
⠄⠄⠄⠄⠄⠄⠄⠈⠉⠁⠈⠉⠉⠙⠿⣿⣿⣿⣿⣿
⠄⠄⠄⠄⠄⠄⠄⠄⣀⣀⣀⠄⠄⠄⠄⠄⠹⣿⣿⣿
⠄⠄⠄⠄⠄⢐⣲⣿⣿⣯⠭⠉⠙⠲⣄⡀⠄⠈⢿⣿
⠐⠄⠄⠰⠒⠚⢩⣉⠼⡟⠙⠛⠿⡟⣤⡳⡀⠄⠄⢻
⠄⠄⢀⣀⣀⣢⣶⣿⣦⣭⣤⣭⣵⣶⣿⣿⣏⠄⠄⣿
⠄⣼⣿⣿⣿⡉⣿⣀⣽⣸⣿⣿⣿⣿⣿⣿⣿⡆⣀⣿
⢠⣿⣿⣿⠿⠟⠛⠻⢿⠿⣿⣿⣿⣿⣿⣿⣿⣿⣶⣼
⠄⣿⣿⣿⡆⠄⠄⠄⠄⠳⡈⣿⣿⣿⣿⣿⣿⣿⣿⣿
⠄⢹⣿⣿⡇⠄⠄⠄⠄⢀⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿
⠄⠄⢿⣿⣷⣨⣽⣭⢁⣡⣿⣿⠟⣩⣿⣿⣿⠿⠿⠟
⠄⠄⠈⡍⠻⣿⣿⣿⣿⠟⠋⢁⣼⠿⠋⠉⠄⠄⠄⠄
⠄⠄⠄⠈⠴⢬⣙⣛⡥⠴⠂⠄⠄⠄⠄⠄⠄⠄⠄⠄...
(the photo of the famous streamer)
Input
Input end with EOF.
Each testcase contains several lines.
First line contains two string S(1<= strlen(S) <= 1000) and p(1<= strlen(q)<=1000)
Second line one integer q(1 <= q <= 200000)
The following are q lines. Each line contain two integer a,b(1<= a <= b <= strlen(S))
Output
For each testcases print the maximum sum from all the queries.
Remember to print \n at the end of each output.