当前位置: 首页 > news >正文

poly模板

#include <iostream>
#include <cstdio>
#include <cstring>
#include <stdlib.h>
#include <algorithm>
#include <vector>
#define int long long
#define N 270004
#define isdigit(ch) ('0' <= ch && ch <= '9')
#define clr(f,n) memset(f,0,sizeof(int) * (n))
#define cpy(f,g,n) memcpy(f,g,sizeof(int) * (n))
using namespace std;
template<typename T>
void read(T&x) {x = 0;int f = 1;char ch = getchar();for (;!isdigit(ch);ch = getchar()) f = (ch == '-' ? -1 : f);for (;isdigit(ch);ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);x *= f;
}
template<typename T>
void write(T x) {if (x < 0) x = -x,putchar('-');if (x > 9) write(x / 10);putchar(x % 10 + '0');
}
int qpow(int a,int b,int mod = 998244353) {int res = 1;while(b) {if (b & 1) res = res * a % mod;a = a * a % mod;b >>= 1;}return res;
}
const int mod = 998244353,G = 3,invg = qpow(G,mod - 2);
void printp(int *f,int n) {for (int i = 0;i <= n;i ++) write(f[i]),putchar(' ');putchar('\n');
} 
int tr[N],tf;
void tpre(int n) {if (n == tf) return;tf = n;for (int i = 0;i < n;i ++)tr[i] = (tr[i >> 1] >> 1) | (i & 1 ? n >> 1 : 0);
}
void ntt(int *f,int n,bool flag) {tpre(n);for (int i = 0;i < n;i ++)if (i < tr[i]) swap(f[i],f[tr[i]]);static int w[N] = {1};for (int p = 2;p <= n;p <<= 1) {int rotate = qpow(flag ? G : invg,(mod - 1) / p),len = p >> 1;for (int i = 1;i < len;i ++) w[i] = w[i - 1] * rotate % mod;for (int st = 0;st < n;st += p)for (int i = st;i < st + len;i ++) {int tt = f[i + len] * w[i - st] % mod;f[i + len] = f[i] - tt;if (f[i + len] < 0) f[i + len] += mod;f[i] = (f[i] + tt) % mod;}} if (!flag) {int invn = qpow(n,mod - 2);for (int i = 0;i < n;i ++) f[i] = f[i] * invn % mod;}
}
void px(int *f,int *g,int n) {for (int i = 0;i <= n;i ++) f[i] = f[i] * g[i] % mod;
}
void mulp(int *f,int *g,int n,int m) {for (m += n,n = 1;n <= m;n <<= 1);ntt(f,n,1),ntt(g,n,1);px(f,g,n);ntt(f,n,0);
}
void invp(int *f,int m) {int n;for (n = 1;n <= m;n <<= 1);static int w[N],r[N],sav[N];w[0] = qpow(f[0],mod - 2);for (int p = 2;p <= n;p <<= 1) {for (int i = 0;i < (p >> 1);i ++) r[i] = w[i] % mod;cpy(sav,f,p);ntt(r,p,1),ntt(sav,p,1);px(r,sav,p);ntt(r,p,0);clr(r,p >> 1);cpy(sav,w,p);ntt(sav,p,1),ntt(r,p,1);px(r,sav,p);ntt(r,p,0);for (int i = p >> 1;i < p;i ++) w[i] = (2 * w[i] - r[i] + mod) % mod;}cpy(f,w,m + 1),clr(sav,n + n),clr(w,n + n),clr(r,n + n);
}
int f[N];
signed main(){int n;cin >> n;for (int i = 0;i <= n;i ++) read(f[i]);invp(f,n),printp(f,n);return 0;
}
http://www.jsqmd.com/news/418443/

相关文章:

  • 2026年DeepSeek推广服务商指南:五家专注AI获客的机构能力梳理 - 品牌2025
  • 2026年广西抖音短视频代运营公司5强推荐榜单公布 - 精选优质企业推荐榜
  • P3031 [USACO11NOV] Above the Median G 题解
  • 2026年青海抖音短视频代运营服务商5强推荐名单公布 - 精选优质企业推荐榜
  • 2026年值得关注的DeepSeek推广服务商推荐:五家AI获客解决方案提供方概览 - 品牌2025
  • 2026年DeepSeek推广服务商推荐清单:五家专注AI获客的机构能力概览 - 品牌2025
  • JAX分布式训练超轻松
  • 2026年AI获客服务商盘点:五家深耕DeepSeek推广的机构能力解析 - 品牌2025
  • 2026年2月双玻百叶玻璃隔断生产商推荐,双层隔音内置百叶 - 品牌鉴赏师
  • 标签脏了,模型再牛也白搭:聊聊训练样本标签质量的评估与修正(把信噪比狠狠干上去)
  • mysql加redis复习
  • 2026年主流DeepSeek推广服务商介绍:五家聚焦AI获客的解决方案提供方 - 品牌2025
  • 2026年值得了解的DeepSeek推广服务商盘点:五家专注AI获客的实战型服务商 - 品牌2025
  • c# 直连solidworks 简单实现
  • pikachu靶场——Cross-Site Scripting-2(Kali系统)
  • 3.27.G(s)传递函数的求解(3-右半平面零点)
  • 从内容到转化如何打通?2026年DeepSeek推广服务商实战能力盘点 - 品牌2025
  • AtCoder Weekday Contest 0004 Beta题解(AWC 0004 Beta A-E)
  • Flutter 布局避坑指南:Text 溢出的罪魁祸首竟然是它!
  • 词找站抄作业大法 和 给 SaaS 定价 9 美元真不多!
  • LangChain 组件详解:RunnablePassthrough
  • 北京GEO服务商有哪些?2026年AI获客方案解析 - 品牌2025
  • AI搜索红利如何抓住?2026年DeepSeek推广服务商能力图谱解析 - 品牌2025
  • AI获客困局如何破局?2026年主流DeepSeek推广服务商全景解析 - 品牌2025
  • 澳洲十佳留学中介机构排名(2026)榜单与点评 - 品牌企业推荐师(官方)
  • 谷歌再次加速:Nano Banana 2 上线,图像生成进入“平民化阶段”
  • 用过才敢说! 降AIGC网站 千笔·降AIGC助手 VS 学术猹,自考党必备!
  • 提示工程反哺AI模型:协同进化视角下,架构师的逆向优化方法论
  • 物理层:传输介质与接入应用
  • ClickHouse如何应对大数据领域的数据倾斜问题