尧图网站建设 
牛客挑战赛 91 · B - 多项式幂级数题目描述小 Code 最近对多项式和生成函数产生了浓厚的兴趣。他定义了一个特殊的多项式$$P(x)\sum_{j1}^{n}x^j$$接着他基于 $P(x)$ 构建了一个无限幂级数$$S(x)\sum_{i1}^{\infty}\Big(P(x)\Big)^i$$现在小 Code 想知道这个幂级数 $S(x)$ 展开后前 $m$ 项的系数分别是多少。由于答案可能很大请将所有系数对 $998\,244\,353$ 取模。更严谨地给定整数 $n$ 和 $m$令多项式 $P(x)x^1x^2\cdotsx^n$并在形式幂级数意义下定义$$S(x)P(x)\big(P(x)\big)^2\big(P(x)\big)^3\cdots$$请计算 $S(x)$ 按 $x$ 的幂展开后 $x^1,x^2,\dots,x^m$ 项的系数并将结果对 $998\,244\,353$ 取模输出。输入描述在一行上输入两个整数 $n,m\left(1\le n,m\le 10^6\right)$。输出描述在一行上输出 $m$ 个整数表示 $x^1,x^2,\cdots,x^m$ 的系数对 $998\,244\,353$ 取模后的值。示例 1输入2 3输出1 2 3示例 2输入3 3输出1 2 4思路首先s收敛故$$S\sum_{i\ge1}P^iP\cdot\sum_{i\ge0}P^i\frac{P}{1-P}$$化一下p$$Px\cdot\frac{1-x^n}{1-x}$$于是$$1-P\frac{(1-x)-x(1-x^n)}{1-x}\frac{1-2xx^{n1}}{1-x}$$$$S\frac{P}{1-P}\frac{x(1-x^n)}{1-x}\cdot\frac{1-x}{1-2xx^{n1}} \frac{x(1-x^n)}{1-2xx^{n1}}$$提取系数$$S\cdot(1-2xx^{n1})x-x^{n1}$$设 $S\sum_{k\ge0}a_kx^k$约定 $a_00$$k0$ 时 $a_k0$比较 $[x^k]$$$a_k-2a_{k-1}a_{k-n-1}[k1]-[kn1]$$即$$\boxed{a_k2a_{k-1}-a_{k-n-1}[k1]-[kn1]}$$逐项 $\mathcal O(1)$总计 $\mathcal O(m)$。参考代码#include bits/stdc.h using namespace std; const int MOD 998244353; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin gt;gt; n gt;gt; m; vectorlt;intgt; a(m 1, 0); for (int k 1; k lt; m; k) { long long v 2LL * a[k - 1] % MOD; if (k - n - 1 gt; 0) v (v - a[k - n - 1] MOD) % MOD; if (k 1) v (v 1) % MOD; if (k n 1) v (v - 1 MOD) % MOD; a[k] (int)v; } for (int k 1; k lt; m; k) cout lt;lt; a[k] lt;lt; \n[k m]; return 0; }总结非常有意思的一道数学题几乎没有什么算法的部分纯是数学推导 屑曾的ACM笔记（2）-数论：多项式、幂级数
牛客挑战赛 91 · B - 多项式幂级数题目描述小 Code 最近对多项式和生成函数产生了浓厚的兴趣。他定义了一个特殊的多项式$$P(x)\sum_{j1}^{n}x^j$$接着他基于 $P(x)$ 构建了一个无限幂级数$$S(x)\sum_{i1}^{\infty}\Big(P(x)\Big)^i$$现在小 Code 想知道这个幂级数 $S(x)$ 展开后前 $m$ 项的系数分别是多少。由于答案可能很大请将所有系数对 $998\,244\,353$ 取模。更严谨地给定整数 $n$ 和 $m$令多项式 $P(x)x^1x^2\cdotsx^n$并在形式幂级数意义下定义$$S(x)P(x)\big(P(x)\big)^2\big(P(x)\big)^3\cdots$$请计算 $S(x)$ 按 $x$ 的幂展开后 $x^1,x^2,\dots,x^m$ 项的系数并将结果对 $998\,244\,353$ 取模输出。输入描述在一行上输入两个整数 $n,m\left(1\le n,m\le 10^6\right)$。输出描述在一行上输出 $m$ 个整数表示 $x^1,x^2,\cdots,x^m$ 的系数对 $998\,244\,353$ 取模后的值。示例 1输入2 3输出1 2 3示例 2输入3 3输出1 2 4思路首先s收敛故$$S\sum_{i\ge1}P^iP\cdot\sum_{i\ge0}P^i\frac{P}{1-P}$$化一下p$$Px\cdot\frac{1-x^n}{1-x}$$于是$$1-P\frac{(1-x)-x(1-x^n)}{1-x}\frac{1-2xx^{n1}}{1-x}$$$$S\frac{P}{1-P}\frac{x(1-x^n)}{1-x}\cdot\frac{1-x}{1-2xx^{n1}} \frac{x(1-x^n)}{1-2xx^{n1}}$$提取系数$$S\cdot(1-2xx^{n1})x-x^{n1}$$设 $S\sum_{k\ge0}a_kx^k$约定 $a_00$$k0$ 时 $a_k0$比较 $[x^k]$$$a_k-2a_{k-1}a_{k-n-1}[k1]-[kn1]$$即$$\boxed{a_k2a_{k-1}-a_{k-n-1}[k1]-[kn1]}$$逐项 $\mathcal O(1)$总计 $\mathcal O(m)$。参考代码#include bits/stdc.h using namespace std; const int MOD 998244353; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin gt;gt; n gt;gt; m; vectorlt;intgt; a(m 1, 0); for (int k 1; k lt; m; k) { long long v 2LL * a[k - 1] % MOD; if (k - n - 1 gt; 0) v (v - a[k - n - 1] MOD) % MOD; if (k 1) v (v 1) % MOD; if (k n 1) v (v - 1 MOD) % MOD; a[k] (int)v; } for (int k 1; k lt; m; k) cout lt;lt; a[k] lt;lt; \n[k m]; return 0; }总结非常有意思的一道数学题几乎没有什么算法的部分纯是数学推导