(2016北京集训十)【xsy1529】小Q与进位制 - 分治FFT

news/2024/4/15 8:14:32

题意很简单,就是求这个数。。。

其实场上我想出了分治fft的正解。。。然而不会打。。。然后打了个暴力fft挂了。。。

没啥好讲的,这题很恶心,卡常卡精度还爆int,要各种优化,有些dalao写的很复杂我都没看懂。。。我写的是每三位拆分然后再合并

代码:

  1 //强烈谴责卡常数而需要大量优化
  2 //upd:还卡精度。。。 
  3 #include<algorithm>
  4 #include<iostream>
  5 #include<cstring>
  6 #include<cstdio>
  7 #include<cmath>
  8 #include<queue>
  9 #define inf 2147483647
 10 #define eps 1e-9
 11 using namespace std;
 12 typedef long long ll;
 13 const double pi=acos(-1);
 14 struct complex{
 15     double a,b;
 16     complex(double _a=0,double _b=0){
 17         a=_a;
 18         b=_b;
 19     }
 20     friend complex operator +(complex x,complex y){return complex(x.a+y.a,x.b+y.b);}
 21     friend complex operator -(complex x,complex y){return complex(x.a-y.a,x.b-y.b);}
 22     friend complex operator *(complex x,complex y){return complex(x.a*y.a-x.b*y.b,x.a*y.b+x.b*y.a);}
 23     friend complex operator *(complex x,double y){return complex(x.a*y,x.b*y);}
 24     friend complex operator /(complex x,double y){return complex(x.a/y,x.b/y);}
 25 };
 26 int n,tot=0,bit,bitnum,rev[1000001],tmp[1000001],A[1000001],B[1000001],bs[120001],a[120001];
 27 char out[2000001];
 28 void fft(complex *s,int op){
 29     for(int i=0;i<bit;i++)if(i<rev[i])swap(s[i],s[rev[i]]);
 30     for(int i=1;i<bit;i<<=1){
 31         complex w(cos(pi/i),op*sin(pi/i));
 32         for(int p=i<<1,j=0;j<bit;j+=p){
 33             complex wk(1,0);
 34             for(int k=j;k<i+j;k++,wk=wk*w){
 35                 complex x=s[k],y=wk*s[k+i];
 36                 s[k]=x+y;
 37                 s[k+i]=x-y;
 38             }
 39         }
 40     }
 41     if(op==-1){
 42         for(int i=0;i<=bit;i++){
 43             s[i]=s[i]/(double)bit;
 44         }
 45     }
 46 }
 47 void mul(int a[],int b[],int c[],int n,int m){
 48     static complex s1[1000001],s2[1000001];
 49     for(bitnum=0,bit=1;bit<=m+n;bit<<=1)bitnum++;
 50     for(int i=0;i<bit;i++){
 51         rev[i]=(rev[i>>1]>>1)|((i&1)<<(bitnum-1));
 52     }
 53     for(int i=0;i<n;i++)s1[i].a=a[i],s1[i].b=0;
 54     for(int i=0;i<m;i++)s2[i].a=b[i],s2[i].b=0;
 55     for(int i=n;i<bit;i++)s1[i].a=s1[i].b=0;
 56     for(int i=m;i<bit;i++)s2[i].a=s2[i].b=0;
 57     fft(s1,1);
 58     fft(s2,1);
 59     for(int i=0;i<bit;i++)s1[i]=s1[i]*s2[i];
 60     fft(s1,-1);
 61     ll p=0;
 62     for(int i=0;i<m+n||p;i++){
 63         p+=(ll)(s1[i].a+0.5);
 64         c[i]=p%1000;
 65         p/=1000;
 66     }
 67 }
 68 void add(int a[],int b[],int n){
 69     int p=0;
 70     for(int i=0;i<n||p;i++){
 71         p+=a[i]+b[i];
 72         a[i]=p%1000;
 73         p/=1000;
 74     }
 75 }
 76 void cdq(int l,int r,int A[],int B[]){
 77     if(l==r){
 78         A[0]=bs[l]%1000;
 79         A[1]=bs[l]/1000%1000;
 80         A[2]=bs[l]/1000000;
 81         B[0]=a[l]%1000;
 82         B[1]=a[l]/1000%1000;
 83         B[2]=a[l]/1000000;
 84         return;
 85     }
 86     int mid=(l+r)/2,ll=(mid-l+2)*2,rr=(r-mid+1)*2;
 87     cdq(l,mid,A,B);
 88     cdq(mid+1,r,A+ll,B+ll);
 89     for(int i=0;i<ll;i++)tmp[i]=B[i];
 90     mul(A,B+ll,B,ll,rr);
 91     add(B,tmp,ll);
 92     mul(A,A+ll,A,ll,rr);
 93 }
 94 void delete_zero(char s[]){
 95     int i,j;
 96     tot--;
 97     for(i=tot;i>=0;i--){
 98         if(s[i]!='0')break;
 99     }
100     s[i+1]=0;
101     j=i;
102     for(i=0;i<j;i++,j--)swap(s[i],s[j]);
103 }
104 int main(){
105     scanf("%d",&n);
106     for(int i=1;i<=n;i++){
107         scanf("%d",&bs[i]);
108     }
109     for(int i=1;i<=n;i++){
110         scanf("%d",&a[i]);
111     }
112     cdq(1,n,A,B);
113     //for(int i=0;i<=n<<1;i++)printf("%d ",B[i]); 
114     for(int i=0;i<=n<<1;i++){
115         for(int j=0;j<3;j++){
116             out[tot++]=B[i]%10+'0';
117             B[i]/=10;
118         }
119     }
120     //delete_zero(out);
121     int i,j;
122     tot--;
123     for(i=tot;i>=0;i--){
124         if(out[i]!='0')break;
125     }
126     out[i+1]=0;
127     j=i;
128     for(i=0;i<j;i++,j--)swap(out[i],out[j]);
129     puts(out);
130     return 0;
131 }

 

转载于:https://www.cnblogs.com/dcdcbigbig/p/9639580.html


http://www.ppmy.cn/news/613855.html

相关文章

php sendmail方法,PHP实现在windows下配置sendmail并通过mail()函数发送邮件的方法

本文实例讲述了PHP实现在windows下配置sendmail并通过mail()函数发送邮件的方法。分享给大家供大家参考&#xff0c;具体如下&#xff1a;1、php mail()函数在windows不能用&#xff0c;需要安装sendmail。2、从http://glob.com.au/sendmail/ 下载sendmail组件3、解压sendmail.…

docker学习(三)常用命令

docker 容器操作 docker环境信息 — docker [info|version] 容器生命周期管理 — docker [create|exec|run|start|stop|restart|kill|rm|pause|unpause] 容器操作管理 — docker [ps|inspect|top|attach|wait|export|port|rename|stat] 容器rootfs命令 — docker [commit|cp|d…

微软BI 之SSIS 系列 - Lookup 组件的使用与它的几种缓存模式 - Full Cache, Partial Cache, NO Cache...

开篇介绍 先简单的演示一下使用 Lookup 组件实现一个简单示例 - 从数据源表 A 中导出数据到目标数据表 B&#xff0c;如果 A 数据在 B 中不存在就插入新数据到B&#xff0c;如果存在就更新B 和 A 表数据保持统一。 随后再来解释在这个过程中使用到的一些术语&#xff0c;以及分…

LCD: 2D-3D匹配算法

LCD: 2D-3D匹配算法 标题&#xff1a;LCD:Learned Cross-Domain Descriptors for 2D-3D Matching 作者&#xff1a;Quang-Hieu Pham, Mikaela Angelina Uy, Binh-Son Hua, et al. 论文地址&#xff1a;https://arxiv.org/abs/1911.09326 摘要 在这项工作中&#xff0c;提出…

2018年爱奇艺校招笔试

我选的是前端方向&#xff0c;所以编程题的题目也比较简单&#xff0c;但是坑很多呀&#xff0c;不知道错在哪&#xff0c;最后没办法直接用最暴力的方法AC了。 笔试分为选择和编程&#xff0c;选择20个&#xff0c;每个三分&#xff0c;编程题两道每道20分。 选择题考点&#…

脱机下载程序

一&#xff0c;脱机下载工具 Mini-Pro V2 版 二&#xff0c;配置stm32CubeIDE 生成hex文件 三&#xff0c;脱机下载步骤 1&#xff0c;连接设备&#xff0c;选择芯片 2&#xff0c; 添加固件。 3&#xff0c;选项字节。 4&#xff0c;生成镜像文件&#xff0c;这个文件包含了…

php http请求xml数据,php获取通过http协议post提交过来xml数据及解析xml

$xml_data ‘‘.‘‘.‘1234567890‘.‘lgsoftwares‘.‘mypassword‘.‘phpmind.com‘.‘‘.‘‘.‘‘.‘‘.‘‘.‘‘.‘JHM‘.‘OGGSHE‘.‘101009‘.‘101509‘.‘1‘.‘‘.‘‘;$URL "https://www.yourwebserver.com/path/";$ch curl_init($URL);curl_setopt(…

如何选择视觉CV光源颜色

如何选择视觉CV光源颜色 一&#xff0e;光源颜色分类 光源颜色的选择对机器视觉光源有什么影响及意义呢&#xff0c;常用的光源颜色有白色&#xff08;W&#xff09;、蓝色&#xff08;B&#xff09;、红色&#xff08;R&#xff09;、绿色&#xff08;G&#xff09;、红外光…

MFC控件编程之复选框单选框分组框

MFC控件编程之复选框单选框分组框 一丶分组框 分组框 英文叫做 GroubBox 添加了分组框主要就是分组.好看.不重点介绍 二丶单选框 英文: Raido Button 单选框需要注意的事项 1.单选框必须设置分组. 在属性中设置. 设置为True 2.如果有两个单选框那么TAB 顺序必须紧邻 VS中设置…

CUDA C编程接口技术分析

CUDA C编程接口技术分析 编程接口 CUDA C为熟悉C编程语言的用户提供了一个简单的路径&#xff0c;可以方便地编写程序供设备执行。 它由C语言的最小扩展集和运行库组成。 核心语言扩展已经引入&#xff1a;cuda c programming guide。它们允许程序员将内核定义为C函数&#…

今晚 7 点半 | SUFS: 存储资源使用量预测服务

线上沙龙 - Paper Reading 第 6 期营业啦 本期直播看点 本期论文>>《SUFS: A Generic Storage Usage Forecasting Service ThroughAdaptive Ensemble Learning》 论文提出了一个增强的 LSTM 神经网络和自适应的模型集成算法&#xff0c;为不同的存储系统提供统的存储资源…

用php做一个简单的汇率,vue实现简单实时汇率计算功能

最近在自己摸索vue的使用&#xff0c;因为相对于只是去看教程和实例&#xff0c;感觉不如自己动手写一个demo入门来的快。刚好看到小程序中有一个简单但是很精致的应用极简汇率&#xff0c;而且它的表现形式和vue的表现形式很像&#xff0c;于是想着自己搞一个简单的应用来试试…

Django框架之第二篇

Django框架之第二篇 一、知识点回顾 1、MTV模型 model&#xff1a;模型&#xff0c;和数据库相关的 template&#xff1a;模板&#xff0c;存放html文件&#xff0c;模板语法&#xff08;目的是将变量如何巧妙的嵌入到HTML页面中&#xff09;。 views&#xff1a;视图函数 另加…

电脑识别指令和代码的原理

电脑识别指令和代码的原理 一&#xff0e;前言 电脑代bai码&#xff0c;就du是让电脑执行的命令。可以让电脑执行相应zhi的命令。就电脑本身底层代码所言就dao是0和1&#xff0c;或者说二进制码、十六进制等等。还有汇编、C、C、java等等高级语言代码。就网络而言有&#xff…

php跨域访问java,案例:PHP Ajax 跨域最佳解决方案

本文通过设置Access-Control-Allow-Origin来实现跨域。例如&#xff1a;客户端的域名是edu.jb51.net&#xff0c;而请求的域名是edu.jb51.net。如果直接使用ajax访问&#xff0c;会有以下错误&#xff1a;XMLHttpRequest cannot load http://edu.jb51.net/server.php. No Acces…

Linux 命令 systemctl 详解

Linux systemctl 命令是 systemd 系统和服务管理器的主要命令之一&#xff0c;它可以启动、停止、重启、重新加载和查询系统服务状态等操作。以下是 systemctl 命令的常用选项和用法&#xff1a; 语法 systemctl [OPTIONS] COMMAND [UNIT]OPTIONS: 可选参数&#xff0c;用于指…

python几种数据类型的取值方式

今天我们主要来学习下python的几种数据类型的取值方式&#xff01; 首先我们先来看下python的几种数据类型&#xff0c;python有五个标准的数据类型&#xff1a; number&#xff08;数字&#xff09;string&#xff08;字符串&#xff09; list&#xff08;列表&#xff09;tup…

毫米波RADAR与LIDAR探秘

毫米波RADAR与LIDAR探秘 说起激光雷达和毫米波雷达&#xff0c;相信业内人士并不陌生&#xff0c;激光雷达是以发射激光束探测目标的位置、速度等特征量的雷达系统。而毫米波雷达是指工作在毫米波波段探测的雷达。毫米波实质上就是电磁波。毫米波的频段比较特殊&#xff0c;其…

狗年拜年php源码,2018狗年拜年词大全!再也不担心拜年没祝词啦~祝您新年快乐!...

原标题&#xff1a;2018狗年拜年词大全&#xff01;再也不担心拜年没祝词啦~祝您新年快乐&#xff01;2018狗年大吉HAPPY NEW YEAR为了您在春节期间能够在第一时间为您的亲朋好友送上祝福~小编已经贴心的为您准备好新年贺词啦&#xff01;有木有很贴心&#xff1f;抓紧时间拿出…

最小化局部边际的合并聚类算法(中篇)

作者&#xff1a;钱烽三、合并聚类算法基于定义2所提出的相似度定义,我们在图2中给出最小化局部边际的合并聚类算法详细执行过程.首先,针对数据集中可能存在的噪声数据,我们对所有样本点进行孤立点检测.然后,作为ACMOM算法的主要过程,我们采用基于MkNN关系的相似度对检测结果为…
最新文章