「Daily OI Round 3」Xor Graph

Luogu

IDLGP10128

Time1000ms

Memory512MB

DifficultyP5

递推洛谷原创O2优化

Xs_siqi 给了你 $2^n$ 个点，$x$ 到 $y$ 有**有向**边当且仅当 $x\operatorname{xor} y=2^k,k \in [0,n)$，且 $x>y$。其中，$\operatorname{xor}$ 表示按位异或，$k$ 为整数。令 $f_{x,y}$ 为 $x$ 点到 $y$ 点的不同路径数，求： $$\sum_{i=1}^{2^n}\sum_{j=1}^{2^n}f_{i,j}(i\neq j)$$ 答案对 $998244353$ 取模。 ## Input 第一行，一个整数 $t$。接下来 $2 \sim t+1$ 行，一行一个整数表示 $n$。 ## Output 共 $t$ 行，每行一个整数表示题目要求的方案数。 [samples] ## Background 在黎明来临之前，总要有人照亮黑暗。 ## Note #### 【样例解释 #1】对于样例的第一组，$3$ 向 $1,2$ 连边，这样 $3$ 到 $1$ 是一个方案，$3$ 到 $2$ 是一个方案，一共有 $2$ 个方案。 #### 【数据范围】对于全部数据保证：$1 \le t \le 10^6$，$1 \le n \le 10^7$。

Samples

Input #1

Output #1

API Response (JSON)

{
  "problem": {
    "name": "「Daily OI Round 3」Xor Graph",
    "description": {
      "content": "Xs_siqi 给了你 $2^n$ 个点，$x$ 到 $y$ 有**有向**边当且仅当 $x\\operatorname{xor} y=2^k,k \\in [0,n)$，且 $x>y$。其中，$\\operatorname{xor}$ 表示按位异或，$k$ 为整数。令 $f_{x,y}$ 为 $x$ 点到 $y$ 点的不同路径数，求：  $$\\sum_{i=1}^{2^n}\\sum_{j=1}^{2",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10128"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Xs_siqi 给了你 $2^n$ 个点，$x$ 到 $y$ 有**有向**边当且仅当 $x\\operatorname{xor} y=2^k,k \\in [0,n)$，且 $x>y$。其中，$\\operatorname{xor}$ 表示按位异或，$k$ 为整数。令 $f_{x,y}$ 为 $x$ 点到 $y$ 点的不同路径数，求： \n\n$$\\sum_{i=1}^{2^n}\\sum_{j=1}^{2...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments