L. The Expected Square

Codeforces

IDCF10288L

Time1000ms

Memory64MB

Difficulty—

English · Original

Formal · Original

Ehab the baby likes playing games with $X O R$ (of course), so he will play the following game. He is given some number $n$. Then, he defines a number $x$ which is initially $0$. In each move, he thinks of a number $r$, where $r$ is a non-negative number strictly less than $2^n$ chosen *uniformly at random*, and changes $x$ to $x plus.circle r$, where $plus.circle$ denotes the bitwise $X O R$ operation. After making the first move, he stops when $x$ becomes $0$ again. Baby Ehab was thinking of the expected value of *the square* of the number of moves that he will play. More formally, let $m$ be the number of moves he plays in a game, then Baby Ehab wants to know $E (m^2)$, Can you know it? Let the answer be represented as $p \/ q$, then you are required to find the value of $p * q^(-1) mod 10^9 + 7$. The first line of input contains $t$, the number of test cases. Each of the following $t$ lines contains one integer, $n$ ($1 <= n <= 10^9)$. For each test case, output the required answer on a single line. ## Input The first line of input contains $t$, the number of test cases.Each of the following $t$ lines contains one integer, $n$ ($1 <= n <= 10^9)$. ## Output For each test case, output the required answer on a single line. [samples]

**Definitions** Let $ n, q \in \mathbb{Z}^+ $ denote the number of nodes and queries, respectively. Let $ T = (V, E) $ be a tree with $ |V| = n $. Let $ w: V \to \{1, 2, \dots, n\} $ be a coloring function assigning a color to each node. For any path $ P_{u,v} \subseteq V $ between nodes $ u $ and $ v $, let $ S = P_{u,v} $ be the set of nodes on the path. A subset $ A \subseteq S $ is *good* if all nodes in $ A $ have distinct colors. Let $ \mathcal{G}(S) $ denote the set of all good subsets of $ S $. **Constraints** 1. $ 1 \leq n, q \leq 5 \times 10^4 $ 2. $ 1 \leq w(u) \leq n $ for all $ u \in V $ 3. The graph is a tree. **Objective** For each query $ (u, v) $, let $ S = P_{u,v} $. Compute: $$ \sum_{A \in \mathcal{G}(S)} |A| \mod 998244353 $$

API Response (JSON)

{
  "problem": {
    "name": "L. The Expected Square",
    "description": {
      "content": "Ehab the baby likes playing games with $X O R$ (of course), so he will play the following game. He is given some number $n$. Then, he defines a number $x$ which is initially $0$. In each move, he thin",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 65536
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10288L"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Ehab the baby likes playing games with $X O R$ (of course), so he will play the following game. He is given some number $n$. Then, he defines a number $x$ which is initially $0$. In each move, he thin...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, q \\in \\mathbb{Z}^+ $ denote the number of nodes and queries, respectively.  \nLet $ T = (V, E) $ be a tree with $ |V| = n $.  \nLet $ w: V \\to \\{1, 2, \\dots, n\\} $ be a colori...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments