시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
30 초 (추가 시간 없음) | 1024 MB | 11 | 5 | 4 | 40.000% |
Games with words and strings are very popular lately. Now Edsger tries to create a similar new game of his own. Here is what he came up with so far.
Edsger's new game is called Palindromic Deletions. As a player of this game, you are given a string of length $N$. Then you will perform the following process $N$ times:
Now Edsger wonders: given a starting string, what is the expected number of candies you will eat during the game?
The first line of the input gives the number of test cases, $T$. $T$ test cases follow. Each test case consists of two lines.
The first line of each test case contains an integer $N$, representing the length of the string.
The second line of each test case contains a string $S$ of length $N$, consisting of lowercase English characters.
For each test case, output one line containing Case #x: E
, where $x$ is the test case number (starting from 1) and $E$ is the expected number of candies you will eat during the game.
$E$ should be computed modulo the prime $10^9+7$ ($1000000007$) as follows. Represent the answer of a test case as an irreducible fraction $\frac{p}{q}$. The number $E$ then must satisfy the modular equation $E×q≡p \pmod{(10^9+7)} $, and be between $0$ and $10^9+6$, inclusive. It can be shown that under the constraints of this problem, such a number $E$ always exists and can be uniquely determined.
2 2 ab 3 aba
Case #1: 2 Case #2: 333333338
In the first test case the game can go in one of two ways (character removed at each step is underlined):
"ab"
→ "a"
→ ""
(where ""
denotes empty string). Both $a$ and ""
are palindromes, so you will eat two candies."ab"
→ "b"
→ ""
. Both $b$ and ""
are palindromes, so you will eat two candies.Overall, the expected number of candies you will eat is $\frac{2+2}{2}=2$ candies.
In the second test case, the game can go in one of six ways (character removed at each step is underlined):
"aba"
→ "ba"
→ "a"
→ ""
"aba"
→ "ba"
→ "b"
→ ""
"aba"
→ "aa"
→ "a"
→ ""
"aba"
→ "aa"
→ "a"
→ ""
"aba"
→ "ab"
→ "b"
→ ""
"aba"
→ "ab"
→ "a"
→ ""
Overall, the expected number of candies you will eat is $\frac{2+2+3+3+2+2}{6}=\frac{14}{6}=\frac{7}{3}$ candies. $333333338$ is a uniquely determined number that satisfies the conditions mentioned in the output section as $333333338×3≡7 \pmod{(10^9+7)}$, therefore $333333338$ is the answer to this test.
Contest > Google > Kick Start > Google Kick Start 2022 > Round C D번