F. Singhal and Broken Keyboard (easy version)

Codeforces

IDCF10276F

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

_If you want to practice topicwise questions in the ladder way like a2oj , do register on my site *http://codedigger.tech* after the contest. Here you will get Handpicked Topicwise Questions from codeforces, codechef, uva and spoj for your better practice. Best of Luck._ _The only difference between easy and hard versions is that you have to tell the number of distinct strings in easy version but you have to tell the number of distinct palindromic string in hard version._ Singhal brings a new keyboard consisting of only two English lowercase letters _a_ and _b_. Somehow keyboard is broken and whenever he press a letter to print on screen , it prints the letter twice or thrice. Example — If he press letter _a_ , then _aa_ or _aaa_ gets printed on the screen with equal probability. He wonders that how many distinct string will be printed on the screen if he press letters of a string $S$ in sequence. Example — If $S =$ _aba_ , then he first press _a_, then _b_ and at last _a_. As the answer can be rather large, print the remainder after dividing it by $1000000007 (10^9 + 7)$. Note : A palindromic string is a string that reads the same backward as forward, for example strings _z_, _aaa_, _aba_, _abccba_ are palindromes, but strings _codedigger_, _codealittle_, _ab_ are not. The first line contains a single integer $t (1 <= t <= 10^5)$ — the number of test cases in the input. Then $t$ test cases follow. Each query contains a single string $S (1 <= | S | <= 10^5)$ consisting of only two letters _a_ and _b_. $| S |$ is the length of the string. It is guaranteed that the total sum of $| S |$ is at most $10^5$. For each test from the input print the number of distinct string modulo $1000000007 (10^9 + 7)$. Print the answers to the tests in the order in which the tests are given in the input. In the first query — The strings which can be print on screen if he press _a_ are _aa_ or _aaa_. In the second query — The strings which can print on screen are _aabb_ or _aaabb_ or _aabbb_ or _aaabbb_. In the last query — The strings which can print on screen are _aaaa_ or _aaaaa_ or _aaaaa_ or _aaaaaa_ . Note that two strings are same , we have to find the distinct strings. ## Input The first line contains a single integer $t (1 <= t <= 10^5)$ — the number of test cases in the input. Then $t$ test cases follow.Each query contains a single string $S (1 <= | S | <= 10^5)$ consisting of only two letters _a_ and _b_. $| S |$ is the length of the string.It is guaranteed that the total sum of $| S |$ is at most $10^5$. ## Output For each test from the input print the number of distinct string modulo $1000000007 (10^9 + 7)$. Print the answers to the tests in the order in which the tests are given in the input. [samples] ## Note In the first query — The strings which can be print on screen if he press _a_ are _aa_ or _aaa_.In the second query — The strings which can print on screen are _aabb_ or _aaabb_ or _aabbb_ or _aaabbb_.In the last query — The strings which can print on screen are _aaaa_ or _aaaaa_ or _aaaaa_ or _aaaaaa_ . Note that two strings are same , we have to find the distinct strings.

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the number of students, $ m \in \mathbb{Z}^+ $ the number of friend pairs. Let $ G = (V, E) $ be an undirected graph with $ |V| = n $, $ |E| = m $, where each vertex represents a student and each edge represents a friendship. Let $ S \subseteq V $ be the selected subset of students attending the conference. **Constraints** 1. $ 1 \leq n \leq 3 \times 10^5 $, $ 1 \leq m \leq 10^6 $ per test case. 2. Total $ \sum n \leq 10^6 $, total $ \sum m \leq 2 \times 10^6 $ across all test cases. 3. Edges are distinct unordered pairs. **Objective** Define the friendly value $ f(S) $ of subset $ S $ as: $$ f(S) = \sum_{\{u,v\} \in E} \left( \mathbf{1}_{u \in S \land v \in S} - \mathbf{1}_{u \in S \oplus v \in S} \right) - |S| $$ Equivalently, let $ d_S(v) $ denote the number of neighbors of $ v $ in $ S $, and $ \deg(v) $ the degree of $ v $ in $ G $. Then: $$ f(S) = \sum_{v \in S} \left( d_S(v) - (\deg(v) - d_S(v)) \right) - |S| = \sum_{v \in S} \left( 2d_S(v) - \deg(v) \right) - |S| $$ Simplify: $$ f(S) = \sum_{v \in S} \left( 2d_S(v) - \deg(v) - 1 \right) $$ **Goal**: Maximize $ f(S) $ over all subsets $ S \subseteq V $.

API Response (JSON)

{
  "problem": {
    "name": "F. Singhal and Broken Keyboard (easy version)",
    "description": {
      "content": "_If you want to practice topicwise questions in the ladder way like a2oj , do register on my site *http://codedigger.tech* after the contest. Here you will get Handpicked Topicwise Questions from code",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10276F"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "_If you want to practice topicwise questions in the ladder way like a2oj , do register on my site *http://codedigger.tech* after the contest. Here you will get Handpicked Topicwise Questions from code...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of students, $ m \\in \\mathbb{Z}^+ $ the number of friend pairs.  \nLet $ G = (V, E) $ be an undirected graph with $ |V| = n $, $ |E| = m $, wh...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments