「ALFR Round 2」D 超立方体

Luogu

IDLGP10588

Time1500ms

Memory512MB

DifficultyP6

数学O2优化组合数学生成函数

那是你与米尔嘉最初的邂逅。一如既往，米尔嘉又给你出了一道数列题。洁白的信封上留着柑橘的芳香，你小心翼翼地拆开信封阅读。 ------------ 在三维中，我们有三维立方体。它的 $2^3$ 个点的坐标都可以写成 $(x,y,z)$ 的形式。同理在 $n$ 维中，我们有 $n$ 维超立方体，它有 $2^n$ 个点。其棱长为 $1$，且所有顶点的各维坐标都是非负整数。我们从点 $(0,0,\dots,0)$ 出发，走过 $m$ 条棱，求到达点 $(1,1,\dots,0)$ 的方案总数。其中要到达的点的坐标中有 $l$ 个数字 $1$。由于答案可能很大，你只需要输出方案数对 $998244353$ 取模后的结果就可以了。 ## Input 第一行为一个整数 $T$，表示数据组数。接下来 $T$ 行，每行三个非负整数 $n,m,l$。 ## Output 对于每组数据，输出一行一个整数答案。 [samples] ## Background > 映入眼帘的是一棵硕大的樱花树。 > > 树下站着一个少女，她正抬头仰望着那棵樱花树。 > 我想：她是位新生吧，大概和我一样也是溜出来的。 > 我也抬着头望了望那棵樱花树。模模糊糊的花色遮住了天空。 > 刮起一阵风，飘舞着的樱花花瓣将少女裹住。 > 少女也看到了我…… ## Note ### 样例解释第一个例子中的 $7$ 种方案分别是： - $(0,0,0) \to (1,0,0) \to (0,0,0) \to (1,0,0)$ - $(0,0,0) \to (0,1,0) \to (0,0,0) \to (1,0,0)$ - $(0,0,0) \to (0,0,1) \to (0,0,0) \to (1,0,0)$ - $(0,0,0) \to (1,0,0) \to (1,1,0) \to (1,0,0)$ - $(0,0,0) \to (1,0,0) \to (1,0,1) \to (1,0,0)$ - $(0,0,0) \to (0,1,0) \to (1,1,0) \to (1,0,0)$ - $(0,0,0) \to (0,0,1) \to (1,0,1) \to (1,0,0)$ ### 数据范围 | 子任务 | 分值 | 限制 | | :----------: | :----------: | :----------: | | $0$ | $10$ | $\sum nm\le2^{26}$，$n\le2^{13}$ | | $1$ | $20$ | $l=0$ | | $2$ | $30$ | $\sum n^2\le2^{26}$ | | $3$ | $40$ | - | 对于 $100\%$ 数据，$1\le T\le600$，$\sum n\log_2 n\le2^{25}$，$n\in[1,2^{21}]$，$m\in[0,2^{64}-1]$，$l\in[0,n]$。 --- 你翻到背面，发现一行小字：请不要忘记考虑特殊情形。

Samples

Input #1

5
3 3 1
3 4 0
114 514 86
19198 10101 7211
604800 4089470473293004800 443520

Output #1

API Response (JSON)

{
  "problem": {
    "name": "「ALFR Round 2」D 超立方体",
    "description": {
      "content": "那是你与米尔嘉最初的邂逅。   一如既往，米尔嘉又给你出了一道数列题。   洁白的信封上留着柑橘的芳香，   你小心翼翼地拆开信封阅读。 ------------ 在三维中，我们有三维立方体。   它的 $2^3$ 个点的坐标都可以写成 $(x,y,z)$ 的形式。   同理在 $n$ 维中，我们有 $n$ 维超立方体，它有 $2^n$ 个点。   其棱长为 $1$，且所有顶点的各维坐标都",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1500,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10588"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "那是你与米尔嘉最初的邂逅。  \n\n一如既往，米尔嘉又给你出了一道数列题。  \n洁白的信封上留着柑橘的芳香，  \n你小心翼翼地拆开信封阅读。\n\n------------\n\n在三维中，我们有三维立方体。  \n它的 $2^3$ 个点的坐标都可以写成 $(x,y,z)$ 的形式。  \n\n同理在 $n$ 维中，我们有 $n$ 维超立方体，它有 $2^n$ 个点。  \n其棱长为 $1$，且所有顶点的各维坐标都...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments