【模板】多项式复合函数（加强版）

Luogu

IDLGP10249

Time10007ms

Memory2048MB

DifficultyP7

多项式O2优化快速傅里叶变换 FFT快速数论变换 NTT模板题

给定一个 $n$ 次多项式 $F(x)$，和一个 $m$ 次多项式 $G(x)$，你需要求一个 $n$ 次多项式 $H(x)$ ，满足条件： $$H(x) \equiv F(G(x))\space (\text{mod }x^{n+1})$$ 换种说法，你要求的多项式应满足： $$H(x) \equiv \sum_{i=0}^n [x^i]F(x)\times G(x)^i \space (\text{mod }x^{n+1})$$ 将结果的各项系数对 $998244353$ 取模。 ## Input 第一行两个正整数 $n,m$，分别表示 $F(x)$ 和 $G(x)$ 的次数。第二行 $n+1$ 个非负整数 $f_i$，表示 $F(x)$ 的 $i$ 次项系数。第三行 $m+1$ 个非负整数 $g_i$，表示 $G(x)$ 的 $i$ 次项系数。 ## Output 输出一行 $n+1$ 个非负整数，从低到高表示 $H(x)$ 的系数。 [samples] ## Background 本题相较于 [P5373](https://www.luogu.com.cn/problem/P5373) 扩大了数据范围。 ## Note **数据范围：** - $1\le m \le n \le 200000$ - $f_i,g_i \in [0,998244353)\cap \mathbb Z$ | 测试点编号 | $m,n\le$ | | :----------: | :----------: | | $1,2$ | $30000$ | | $3,4$ | $50000$ | | $5,6$ | $100000$ | | $7,8$ | $150000$ | | $9,10$ | $200000$ |

Samples

Input #1

4 3
1 2 3 4 5
1 2 3 4

Output #1

15 80 300 892 2069

API Response (JSON)

{
  "problem": {
    "name": "【模板】多项式复合函数（加强版）",
    "description": {
      "content": "给定一个 $n$ 次多项式 $F(x)$，和一个 $m$ 次多项式 $G(x)$，你需要求一个 $n$ 次多项式 $H(x)$ ，满足条件：   $$H(x) \\equiv F(G(x))\\space (\\text{mod }x^{n+1})$$    换种说法，你要求的多项式应满足：   $$H(x) \\equiv \\sum_{i=0}^n [x^i]F(x)\\times G(x)^i \\spa",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 10007,
      "memory_limit": 2097152
    },
    "difficulty": {
      "LuoguStyle": "P7"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10249"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给定一个 $n$ 次多项式 $F(x)$，和一个 $m$ 次多项式 $G(x)$，你需要求一个 $n$ 次多项式 $H(x)$ ，满足条件：  \n$$H(x) \\equiv F(G(x))\\space (\\text{mod }x^{n+1})$$   \n换种说法，你要求的多项式应满足：  \n$$H(x) \\equiv \\sum_{i=0}^n [x^i]F(x)\\times G(x)^i \\spa...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments