[UESTCPC 2024] Add

Luogu
IDLGP10329
Time1000ms
Memory256MB
DifficultyP3
数学递推2024O2优化高校校赛
给定一个长度为 $n$ 的序列 $a_1,a_2,\ldots,a_n$,初始时 $a_i=i$。对该序列进行 $n-1$ 次操作,其中第 $i$ 次操作为在 $[1,n-i]$ 中等概率选择一个整数 $j$,令 $a_j$ 变为 $a_j+2a_{n-i+1}$。 求操作完毕后 $a_1$ 的期望 $\bmod\text{ }998244353$ 的值。 ## Input 输入第一行一个正整数 $T$ $(1\leq T\leq 10^4)$,表示数据组数。 接下来 $T$ 组数据,每组一行一个正整数 $n$ $(1\leq n\leq 10^9)$,表示序列的长度。 ## Output $T$ 行,每行一个整数表示 $a_1$ 的期望 $\bmod\text{ }998244353$ 的值。 [samples]
Samples
Input #1
3
4
2
5
Output #1
30
5
55
Input #2
3
4
3
5
Output #2
30
14
55
Input #3
3
8
1
3
Output #3
204
1
14
API Response (JSON)
{
  "problem": {
    "name": "[UESTCPC 2024] Add",
    "description": {
      "content": "给定一个长度为 $n$ 的序列 $a_1,a_2,\\ldots,a_n$,初始时 $a_i=i$。对该序列进行 $n-1$ 次操作,其中第 $i$ 次操作为在 $[1,n-i]$ 中等概率选择一个整数 $j$,令 $a_j$ 变为 $a_j+2a_{n-i+1}$。 求操作完毕后 $a_1$ 的期望 $\\bmod\\text{ }998244353$ 的值。",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": {
      "LuoguStyle": "P3"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10329"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给定一个长度为 $n$ 的序列 $a_1,a_2,\\ldots,a_n$,初始时 $a_i=i$。对该序列进行 $n-1$ 次操作,其中第 $i$ 次操作为在 $[1,n-i]$ 中等概率选择一个整数 $j$,令 $a_j$ 变为 $a_j+2a_{n-i+1}$。\n\n求操作完毕后 $a_1$ 的期望 $\\bmod\\text{ }998244353$ 的值。\n\n## Input\n\n输入第一行一个正...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments