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

NTT学习笔记(快速数论变换)

一些概念

欧拉函数 ϕ ( n ) \phi(n) ϕ(n)

欧拉函数简介

g g g n n n互质,则令 g x % n = 1 g^x\%n=1 gx%n=1的最小正整数 x x x称为 g g g n n n的阶。

原根

对于互质的两个正整数 g g g n n n,如果 g g g n n n的阶为 ϕ ( n ) \phi(n) ϕ(n),则称 g g g n n n的原根。

求原根

一般的原根都比较小,暴力枚举即可。


NTT

前置知识:快速傅里叶变换( F F T FFT FFT

F F T FFT FFT中,我们选择 n n n次单位复根作为 x x x的值,因为他们满足消去引理、折半引理、求和引理,所以可以用分治的方法将时间复杂度变为 O ( n log ⁡ n ) O(n\log n) O(nlogn)。但因为用了复数,所以在精度上有误差。而在一些题目要求的是带模的多项式乘法,所以 F F T FFT FFT就用不了了。那么,我们能不能让 x x x取整数值,使得这个值也能满足消去引理、折半引理、求和引理呢?

ϕ ( m ) = r × 2 d \phi(m)=r\times 2^d ϕ(m)=r×2d,令 n = 2 d n=2^d n=2d x n i = x ϕ ( m ) × i / n ( m o d m ) x_n^i=x^{\phi(m)\times i/n}\pmod m xni=xϕ(m)×i/n(modm),其中 i ≤ n i\leq n in

x n i x_n^i xni有以下性质:

1. 消去引理

x d n d k = x n k ( m o d m ) x_{dn}^{dk}=x_n^k\pmod m xdndk=xnk(modm)

证明: x d n d k = x ϕ ( m ) × d k / d n = x ϕ ( m ) × k / n = x n k ( m o d m ) x_{dn}^{dk}=x^{\phi(m)\times dk/dn}=x^{\phi(m)\times k/n}=x_n^k\pmod m xdndk=xϕ(m)×dk/dn=xϕ(m)×k/n=xnk(modm)

2. 折半引理

( x n k + n / 2 ) 2 = x n / 2 k ( m o d m ) (x_n^{k+n/2})^2=x_{n/2}^k \pmod m (xnk+n/2)2=xn/2k(modm)

证明: ( x n k + n / 2 ) 2 = x n 2 k + n = x n 2 k = x n / 2 k ( m o d m ) (x_n^{k+n/2})^2=x_n^{2k+n}=x_n^{2k}=x_{n/2}^k\pmod m (xnk+n/2)2=xn2k+n=xn2k=xn/2k(modm)

3. 求和引理

∑ i = 0 n − 1 ( x n k ) j = 0 ( m o d m ) \sum\limits_{i=0}^{n-1}(x_n^k)^j=0\pmod m i=0n1(xnk)j=0(modm)

证明: ∑ i = 0 n − 1 ( x n k ) j = 1 − ( x n k ) n 1 − x n k = 0 1 − x n k = 0 \sum\limits_{i=0}^{n-1}(x_n^k)^j=\dfrac{1-(x_n^k)^n}{1-x_n^k}=\dfrac{0}{1-x_n^k}=0 i=0n1(xnk)j=1xnk1(xnk)n=1xnk0=0


那么,用 x x x来代替 F F T FFT FFT中的 ω \omega ω,其他不变,就可以求带模数的多项式乘法了。

模数的限制

若模数 m = r × 2 k + 1 m=r\times 2^k+1 m=r×2k+1(其中 r r r为奇数, k k k为整数),则多项式乘积的次数不能超过 2 k 2^k 2k

如果题目没有模数,那也可以取一个较大的模数,保证答案的每一位都小于这个模数,用这个模数来做 N T T NTT NTT也是可以的。

一些模数的原根

模数原根最大长度
998244353 = 119 × 2 23 + 1 998244353=119\times 2^{23}+1 998244353=119×223+1 3 3 3 2 23 2^{23} 223
469762049 = 7 × 2 26 + 1 469762049=7\times 2^{26}+1 469762049=7×226+1 3 3 3 2 26 2^{26} 226
2281701377 = 17 × 2 27 + 1 2281701377=17\times 2^{27}+1 2281701377=17×227+1 3 3 3 2 27 2^{27} 227

例题

多项式乘法(FFT)

#include<bits/stdc++.h>
using namespace std;
const long long g=3,mod=998244353;
long long w,wn,a1[5000005],a2[5000005];
long long mi(long long t,long long v){if(v==0) return 1;long long re=mi(t,v/2);re=re*re%mod;if(v&1) re=re*t%mod;return re;
}
void ch(long long *a,int l){for(int i=1,j=l/2,k;i<l-1;i++){if(i<j) swap(a[i],a[j]);k=l/2;while(j>=k){j-=k;k>>=1;}j+=k;}
}
void ntt(long long *a,int l,int fl){for(int i=2;i<=l;i<<=1){if(fl==1) wn=mi(g,(mod-1)/i);else wn=mi(g,mod-1-(mod-1)/i);for(int j=0;j<l;j+=i){w=1;for(int k=j;k<j+i/2;k++,w=w*wn%mod){long long t=a[k],u=w*a[k+i/2]%mod;a[k]=(t+u)%mod;a[k+i/2]=(t-u+mod)%mod;}}}if(fl==-1){long long ny=mi(l,mod-2);for(int i=0;i<l;i++) a[i]=a[i]*ny%mod;}
}
int main()
{int n=1,l1,l2;scanf("%d%d",&l1,&l2);++l1;++l2;while(n<l1+l2) n<<=1;for(int i=0;i<l1;i++){scanf("%lld",&a1[i]);}for(int i=0;i<l2;i++){scanf("%lld",&a2[i]);}ch(a1,n);ch(a2,n);ntt(a1,n,1);ntt(a2,n,1);for(int i=0;i<n;i++){a1[i]=a1[i]*a2[i]%mod;}ch(a1,n);ntt(a1,n,-1);for(int i=0;i<l1+l2-1;i++) printf("%lld ",a1[i]);return 0;
}

相关文章:

NTT学习笔记(快速数论变换)

一些概念 欧拉函数 ϕ ( n ) \phi(n) ϕ(n) 欧拉函数简介 阶 若 g g g和 n n n互质&#xff0c;则令 g x % n 1 g^x\%n1 gx%n1的最小正整数 x x x称为 g g g模 n n n的阶。 原根 对于互质的两个正整数 g g g和 n n n&#xff0c;如果 g g g模 n n n的阶为 ϕ ( n ) \phi…...

Android类似微信首页的页面开发教程(Kotlin)二

前提条件 安装并配置好Android Studio Android Studio Electric Eel | 2022.1.1 Patch 2 Build #AI-221.6008.13.2211.9619390, built on February 17, 2023 Runtime version: 11.0.150-b2043.56-9505619 amd64 VM: OpenJDK 64-Bit Server VM by JetBrains s.r.o. Windows 11 …...

PAt A1015 Reversible Primes

1015 Reversible Primes 分数 20 作者 CHEN, Yue 单位 浙江大学 A reversible prime in any number system is a prime whose "reverse" in that number system is also a prime. For example in the decimal system 73 is a reversible prime because its rever…...

解决Lemuroid识别不到蓝牙键盘的问题

Android系统基于libretro的全能游戏模拟器&#xff0c;目前有RetroArch&#xff0c;Kodi&#xff0c;Lemuroid。 而且这三个都是开源免费的APP。 Lemuroid相对前面两个功能比较简陋。也不能自己下载核心。但代码也是最少的。 在使用Lemuroid的时候&#xff0c;发现它不能检测…...

SpringBoot 使用 Sa-Token 完成权限认证

一、设计思路 所谓权限认证&#xff0c;核心逻辑就是判断一个账号是否拥有指定权限&#xff1a; 有&#xff0c;就让你通过。没有&#xff1f;那么禁止访问&#xff01; 深入到底层数据中&#xff0c;就是每个账号都会拥有一个权限码集合&#xff0c;框架来校验这个集合中是…...

Spring核心与设计思想、创建与使用

文章目录 一、Spring是什么二、为什么要学习框架三、IoC和DI&#xff08;一&#xff09;IoC1. 认识IoC2. Spring的核心功能 &#xff08;二&#xff09;DI 四、Spring项目的创建&#xff08;一&#xff09;使用 Maven 方式创建一个 Spring 项目 五、Spring项目的使用&#xff0…...

mysql 备份 还原

1:备份 执行命令方案1: /usr/local/mysql/bin/mysqldump -uX -pX -h 127.0.0.1 --set-gtid-purgedOFF --skip-extended-insert --add-drop-table --add-locks --create-options --disable-keys --lock-tables --quick --set-charset -e --max_allowed_packet16777216 --net_b…...

每日学术速递4.26

CV - 计算机视觉 | ML - 机器学习 | RL - 强化学习 | NLP 自然语言处理 Subjects: cs.CV 1.AutoNeRF: Training Implicit Scene Representations with Autonomous Agents 标题&#xff1a;AutoNeRF&#xff1a;使用自主代理训练隐式场景表示 作者&#xff1a;Pierre Marz…...

RabbitMQ使用StringRedisTemplate-防止重复消费

造成重复消费的原因&#xff1a; MQ向消费者推送message&#xff0c;消费者向MQ返回ack&#xff0c;告知所推送的消息消费成功。但是由于网络波动等原因&#xff0c;可能造成消费者向MQ返回的ack丢失。MQ长时间&#xff08;一分钟&#xff09;收不到ack&#xff0c;于是会向消…...

临沂大学张继群寄语

目录 寄语 1、不能有不良睹好 2、坚毅的个性和勤奋的品质 3、会存钱...

线程学习笔记

1:Thread 线程的生命周期控制 2:Runnable 可执行的任务和程序 3:Callable 执行程序后返回结果 4:Future 收集程序返回结果 5:Executor 线程池 6:ForkJoin 默认线程池 每个线程有工作队列 工作窃取 7:RunnableFuture FutureTask 实现 Runnable 和 Future 执…...

代码随想录算法训练营第四十二天|01背包问题,你该了解这些!、01背包问题,你该了解这些! 滚动数组 、416. 分割等和子集

文章目录 01背包问题&#xff0c;你该了解这些&#xff01;01背包问题&#xff0c;你该了解这些&#xff01; 滚动数组416. 分割等和子集 01背包问题&#xff0c;你该了解这些&#xff01; 题目链接&#xff1a;代码随想录 二维数组解决0-1背包问题 解题思路&#xff1a; 1.dp…...

结构体指针、数组指针和结构体数组指针

结构体指针 首先让我们定义结构体&#xff1a; struct stu { char name[20]; long number; float score[4]; }; 再定义指向结构体类型变量的指针变量&#xff1a; struct stu *student; /*定义结构体类型指针*/ student malloc(sizeof(struct stu)); /*为指针变量分…...

项目架构一些注意点

考虑系统的 稳定性 一、微服务的稳定性 1、如何解决那些不稳定的因素/问题&#xff1f;也是常说的如何容错。 2、一个系统的高可用取决于它本身和其强依赖的组件的高可用 3、消除单点 保活机制 健康检查 注册中心如何保障稳定性 注册中心集群 微服务本身对注册信息的本地持…...

Forefront GPT-4免费版:开启无限畅聊时代,乐享人工智能快感,无限制“白嫖”,还能和N多角色一起聊天?赶紧注册,再过些时间估计就要收费了

目录 前言注册登录方式应用体验聊天体验绘图体验 “是打算先免费后收费吗&#xff1f;”建议其它资料下载 前言 近期&#xff0c;人工智能技术迎来重大飞跃&#xff0c;OpenAI的ChatGPT等工具成为全球数亿人探索提高生产力和增强创造力的新方法。人们现在可以使用人工智能驱动…...

深入浅出 Compose Compiler(1) Kotlin Compiler KCP

前言 Compose 的语法简洁、代码效率非常高&#xff0c;这主要得益于 Compose Compiler 的一系列编译期魔法&#xff0c;帮开发者生成了很多样板代码。但编译期插桩也阻碍了我们对于 Compose 运行原理的认知&#xff0c;想要真正读懂 Compose 就必须先了解它的 Compiler。本系列…...

BatchNormalization和LayerNormalization的理解、适用范围、PyTorch代码示例

文章目录 为什么要NormalizationBatchNormLayerNormtorch代码示例 学习神经网络归一化时&#xff0c;文章形形色色&#xff0c;但没找到适合小白通俗易懂且全面的。学习过后&#xff0c;特此记录。 为什么要Normalization 当输入数据量级极大或极小时&#xff0c;为保证输出数…...

大数据 | 实验二:文档倒排索引算法实现

文章目录 &#x1f4da;实验目的&#x1f4da;实验平台&#x1f4da;实验内容&#x1f407;在本地编写程序和调试&#x1f955;代码框架思路&#x1f955;代码实现 &#x1f407;在集群上提交作业并执行&#x1f955;在集群上提交作业并执行&#xff0c;同本地执行相比即需修改…...

Java文档注释-JavaDoc标签

标签含义author指定作者{code}使用代码字体以原样显示信息&#xff0c;不处理HTML样式deprecated指定程序元素已经过时{docRoot}指定当前文档的根目录路径exception标识由方法或构造函数抛出的异常{inheritDoc}从直接超类中继承注释{link}插入指向另外一个主题的内联链接{linkp…...

黑盒测试过程中【测试方法】详解5-输入域,输出域,猜错法

在黑盒测试过程中&#xff0c;有9种常用的方法&#xff1a;1.等价类划分 2.边界值分析 3.判定表法 4.正交实验法 5.流程图分析 6.因果图法 7.输入域覆盖法 8.输出域覆盖法 9.猜错法 黑盒测试过程中【测试方法】讲解1-等价类&#xff0c;边界值&#xff0c;判定表_朝一…...

idea大量爆红问题解决

问题描述 在学习和工作中&#xff0c;idea是程序员不可缺少的一个工具&#xff0c;但是突然在有些时候就会出现大量爆红的问题&#xff0c;发现无法跳转&#xff0c;无论是关机重启或者是替换root都无法解决 就是如上所展示的问题&#xff0c;但是程序依然可以启动。 问题解决…...

从WWDC看苹果产品发展的规律

WWDC 是苹果公司一年一度面向全球开发者的盛会&#xff0c;其主题演讲展现了苹果在产品设计、技术路线、用户体验和生态系统构建上的核心理念与演进脉络。我们借助 ChatGPT Deep Research 工具&#xff0c;对过去十年 WWDC 主题演讲内容进行了系统化分析&#xff0c;形成了这份…...

逻辑回归:给不确定性划界的分类大师

想象你是一名医生。面对患者的检查报告&#xff08;肿瘤大小、血液指标&#xff09;&#xff0c;你需要做出一个**决定性判断**&#xff1a;恶性还是良性&#xff1f;这种“非黑即白”的抉择&#xff0c;正是**逻辑回归&#xff08;Logistic Regression&#xff09;** 的战场&a…...

为什么需要建设工程项目管理?工程项目管理有哪些亮点功能?

在建筑行业&#xff0c;项目管理的重要性不言而喻。随着工程规模的扩大、技术复杂度的提升&#xff0c;传统的管理模式已经难以满足现代工程的需求。过去&#xff0c;许多企业依赖手工记录、口头沟通和分散的信息管理&#xff0c;导致效率低下、成本失控、风险频发。例如&#…...

【算法训练营Day07】字符串part1

文章目录 反转字符串反转字符串II替换数字 反转字符串 题目链接&#xff1a;344. 反转字符串 双指针法&#xff0c;两个指针的元素直接调转即可 class Solution {public void reverseString(char[] s) {int head 0;int end s.length - 1;while(head < end) {char temp …...

unix/linux,sudo,其发展历程详细时间线、由来、历史背景

sudo 的诞生和演化,本身就是一部 Unix/Linux 系统管理哲学变迁的微缩史。来,让我们拨开时间的迷雾,一同探寻 sudo 那波澜壮阔(也颇为实用主义)的发展历程。 历史背景:su的时代与困境 ( 20 世纪 70 年代 - 80 年代初) 在 sudo 出现之前,Unix 系统管理员和需要特权操作的…...

JUC笔记(上)-复习 涉及死锁 volatile synchronized CAS 原子操作

一、上下文切换 即使单核CPU也可以进行多线程执行代码&#xff0c;CPU会给每个线程分配CPU时间片来实现这个机制。时间片非常短&#xff0c;所以CPU会不断地切换线程执行&#xff0c;从而让我们感觉多个线程是同时执行的。时间片一般是十几毫秒(ms)。通过时间片分配算法执行。…...

【HarmonyOS 5 开发速记】如何获取用户信息(头像/昵称/手机号)

1.获取 authorizationCode&#xff1a; 2.利用 authorizationCode 获取 accessToken&#xff1a;文档中心 3.获取手机&#xff1a;文档中心 4.获取昵称头像&#xff1a;文档中心 首先创建 request 若要获取手机号&#xff0c;scope必填 phone&#xff0c;permissions 必填 …...

Reasoning over Uncertain Text by Generative Large Language Models

https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829 1. 概述 文本中的不确定性在许多语境中传达,从日常对话到特定领域的文档(例如医学文档)(Heritage 2013;Landmark、Gulbrandsen 和 Svenevei…...

技术栈RabbitMq的介绍和使用

目录 1. 什么是消息队列&#xff1f;2. 消息队列的优点3. RabbitMQ 消息队列概述4. RabbitMQ 安装5. Exchange 四种类型5.1 direct 精准匹配5.2 fanout 广播5.3 topic 正则匹配 6. RabbitMQ 队列模式6.1 简单队列模式6.2 工作队列模式6.3 发布/订阅模式6.4 路由模式6.5 主题模式…...