概述
写在前面
“模板库”这一系列文章用来复习
O
I
OI
OI模板
由于时间原因，作者无法一一亲自调试其中的程序，也因如此，有一部分程序来自于互联网，如果您觉得这侵犯了您的合法权益，请联系
(
Q
Q
2068926345
)
(QQ2068926345)
(QQ2068926345)删除。
对于给您造成的不便和困扰，我表示深深的歉意。
本系列文章仅用于学习，禁止任何人或组织用于商业用途。
本系列文章中，标记*的为选学算法，在
N
O
I
P
NOIP
NOIP中较少涉及。
字符串算法
KMP匹配算法
【简介】
K
M
P
KMP
KMP算法是一种改进的字符串匹配算法，由
D
.
E
.
K
n
u
t
h
，
J
.
H
.
M
o
r
r
i
s
D.E.Knuth，J.H.Morris
D.E.Knuth，J.H.Morris和
V
.
R
.
P
r
a
t
t
V.R.Pratt
V.R.Pratt同时发现，因此人们称它为克努特——莫里斯——普拉特操作（简称
K
M
P
KMP
KMP算法）。
K
M
P
KMP
KMP算法的关键是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。
具体实现就是实现一个
n
e
x
t
(
)
next()
next()函数，函数本身包含了模式串的局部匹配信息。时间复杂度
Θ
(
m
+
n
)
Theta(m+n)
Θ(m+n)。
【代码实现】
//problemID:https://www.luogu.org/problemnew/show/P3375
#include<cstdio>
#include<cstring>
char s[1000007],s1[1000007];
int next[1000007];
int len,len1,ans;
void get_next(){
int j=0;
for(int i=2;i<=len1;++i){
while(j && s1[i]!=s1[j+1])j=next[j];
if(s1[i]==s1[j+1])++j;
next[i]=j;
}
}
void kmp(){
int j=0;
for(int i=1;i<=len;++i){
while(j && s[i]!=s1[j+1])j=next[j];
if(s[i]==s1[j+1])++j;
if(j==len1)printf("%dn",i-j+1),j=next[j];
}
for(int i=1;i<=len1;++i)printf("%d ",next[i]);
}
int main(){
scanf("%s%s",s+1,s1+1);
len=strlen(s+1);
len1=strlen(s1+1);
get_next();
kmp();
return 0;
}
复杂度 Θ ( m + n ) Theta(m+n) Θ(m+n)
Manacher算法
【简介】
M a n a c h a r Manachar Manachar算法主要是处理字符串中关于回文串的问题的，它可以在 Θ ( n ) Theta(n) Θ(n)的时间处理出以字符串中每一个字符为中心的回文串半径，由于将原字符串处理成两倍长度的新串，在每两个字符之间加入一个特定的特殊字符，因此原本长度为偶数的回文串就成了以中间特殊字符为中心的奇数长度的回文串了。
【代码实现】
//problemID:https://www.luogu.org/problemnew/show/P3805
#include<iostream>
#include<cstdio>
#include<ctype.h>
#include<cstring>
using namespace std;
int p[22000007];
char s[22000007],ss[11000007];
void manacher(int l){
int ans=0,mid=0,mx=-1;
for(int i=0;i<=l;++i){
if(mid+mx>i)p[i]=min(p[(mid<<1)-i],mid+mx-i);
while(i-p[i]-1>=0 && s[i-p[i]-1]==s[i+p[i]+1])p[i]++;
if(mid+mx<i+p[i])mid=i,mx=p[i];
ans=max(ans,p[i]);
}
printf("%d",ans);
}
int main(){
scanf("%s",ss);
int len=strlen(ss),l=-1;
for(int i=0;i<len;i++) s[++l]='#',s[++l]=ss[i];
s[++l]='#';
manacher(l);
return 0;
}
复杂度 Θ ( n ) Theta(n) Θ(n)
字符串hash
【简介】
H a s h Hash Hash，有时译做“散列”，也有直接音译为“哈希”的，就是把任意长度的输入（又叫做预映射 p r e − i m a g e pre-image pre−image）通过散列算法变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不可能从散列值来确定唯一的输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。
【代码实现】
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef unsigned long long ull;
ull base=137;
struct data{
ull x,y;
bool operator <(data b)const{return x<b.x;}
}a[10007];
char s[10007];
int n,ans=1;
ull mod1=19260817;
ull mod2=19660813;
ull hash1(char s[]){
int len=strlen(s);
ull ans=0;
for(int i=0;i<len;++i)ans=(ans*base+(ull)s[i])%mod1;
return ans;
}
ull hash2(char s[]){
int len=strlen(s);
ull ans=0;
for(int i=0;i<len;i++)ans=(ans*base+(ull)s[i])%mod2;
return ans;
}
signed main(){
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%s",s);
a[i].x=hash1(s);
a[i].y=hash2(s);
}
sort(a+1,a+n+1);
for(int i=2;i<=n;++i)
if(a[i].x!=a[i-1].x || a[i-1].y!=a[i].y)ans++;
printf("%dn",ans);
return 0;
}
Trie树
【简介】
又称单词查找树， T r i e Trie Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。
【代码实现】
#include<cstring>
#include<iostream>
#include<conio.h>
using namespace std;
namespace trie
{
template<classT,size_t CHILD_MAX>
/*
ParameterT:Typeofreserveddata.
ParameterCHILD_MAX:Sizeofarryofpointerstochildnode.
*/
struct nod
{
Treserved;
nod<T,CHILD_MAX>*child[CHILD_MAX];
nod()
{
memset(this,0,sizeof*this);
}
~nod()
{
for(unsignedi=0; i<CHILD_MAX; i++)
deletechild[i];
}
void Traversal(char*str,unsignedindex)
{
unsignedi;
for(i=0; i<index; i++)
cout<<str[i];
cout<<'t'<<reserved<<endl;
for(i=0; i<CHILD_MAX; i++)
{
if(child[i])
{
str[index]=i;
child[i]->Traversal(str,index+1);
}
}
return;
}
};
template<classT,size_t CHILD_MAX=127>
/*
ParameterT:Typeofreserveddata.
ParameterCHILD_MAX:Sizeofarryofpointerstochildnode.
*/
classtrie
{
private:
nod<T,CHILD_MAX>root;
public:
nod<T,CHILD_MAX>*AddStr(char*str);
nod<T,CHILD_MAX>*FindStr(char*str);
boolDeleteStr(char*str);
void Traversal()
{
char str[100];
root.Traversal(str,0);
}
};
template<classT,size_tCHILD_MAX>
nod<T,CHILD_MAX>*trie<T,CHILD_MAX>::AddStr(char*str)
{
nod<T,CHILD_MAX>*now=&root;
do
{
if(now->child[*str]==NULL)
now->child[*str]=newnod<T,CHILD_MAX>;
now=now->child[*str];
}
while(*(++str)!=' ');
return now;
}
template<classT,size_tCHILD_MAX>
nod<T,CHILD_MAX>*trie<T,CHILD_MAX>::FindStr(char*str)
{
nod<T,CHILD_MAX>*now=&root;
do
{
if(now->child[*str]==NULL)
return NULL;
now=now->child[*str];
}
while(*(++str)!=' ');
returnnow;
}
template<classT,size_tCHILD_MAX>
bool trie<T,CHILD_MAX>::DeleteStr(char*str)
{
nod<T,CHILD_MAX>**nods=new nod<T,CHILD_MAX>*[strlen(str)];
intsnods=1;
nod<T,CHILD_MAX>*now=&root;
nods[0]=&root;
do
{
if(now->child[*str]==NULL)
returnfalse;
nods[snods++]=now=now->child[*str];
}
while(*(++str)!=' ');
snods--;
while(snods>0)
{
for(unsigned i=0; i<CHILD_MAX; i++)
if(nods[snods]->child[i]!=NULL)
return true;
delete nods[snods];
nods[--snods]->child[*(--str)]=NULL;
}
return true;
}
}
int main()
{
//TestProgram
trie::trie<int>tree;
while(1)
{
cout<<"1foraddastring"<<endl;
cout<<"2forfindastring"<<endl;
cout<<"3fordeleteastring"<<endl;
cout<<"4fortraversal"<<endl;
cout<<"5forexit"<<endl;
charstr[100];
switch(getch())
{
case '1':
cin.getline(str,100);
cout<<"Thisstinghasexistedfor"<<tree.AddStr(str)->reserved++<<"times."<<endl;
break;
case '2':
cin.getline(str,100);
trie::nod<int,127>*find;
find=tree.FindStr(str);
if(!find)
cout<<"Nofound."<<endl;
else
cout<<"Thisstinghasexistedfor"<<find->reserved<<"times."<<endl;
break;
case '3':
cin.getline(str,100);
cout<<"Theactionis"<<(tree.DeleteStr(str)?"Successful.":"Unsuccessful.")<<endl;
break;
case '4':
tree.Traversal();
break;
case '5':
return 0;
}
}
return 0;
}
//https://www.luogu.org/problem/P2922
#include<iostream>
using namespace std;
int trie[500007][2];
int v[500007],vv[500007];
int n,m,tot=1;
inline int read(){
int x=0,f=0;char ch=getchar();
while(!isdigit(ch))f|=ch=='-',ch=getchar();
while(isdigit(ch))x=x*10+(ch^48),ch=getchar();
return f?-x:x;
}
void insert(bool s[],int l){
int rt=1;
for(int i=0;i<l;++i){
int x=s[i];
if(!trie[rt][x])trie[rt][x]=++tot;
rt=trie[rt][x];
vv[rt]++;
}
v[rt]++;
}
inline void find(bool s[],int l){
int rt=1,ans=0,f=1;
for(int i=0;i<l;++i){
int x=s[i];
if(!trie[rt][x]){
f=0;break;
}
rt=trie[rt][x];
if(f)ans+=v[rt];
}
if(f)ans+=vv[rt]-v[rt];
printf("%dn",ans);
}
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;++i){
int o=read();
bool s[10007];
for(int i=0;i<o;++i)s[i]=read();
insert(s,o);
}
for(int i=1;i<=m;++i){
int o=read();
bool s[10007];
for(int i=0;i<o;++i)s[i]=read();
find(s,o);
}
return 0;
}
*后缀数组
【简介】
在字符串处理当中，后缀树和后缀数组都是非常有力的工具。其实后缀数组是后缀树的一个非常精巧的替代品，它比后缀树容易编程实现，能够实现后缀树的很多功能而时间复杂度也不太逊色，并且，它比后缀树所占用的空间小很多。可以说，在信息学竞赛中后缀数组比后缀树要更为实用。
【代码实现】
//problemID:https://www.luogu.org/problemnew/show/P3809
#include<iostream>
#include<cstdio>
#include<ctype.h>
#include<cstring>
using namespace std;
char s[1000007];
int rak[2000007],sa[1000007],tp[2000007];
int tax[1000007];
int N,M;
inline void Bucket_Sort(){
for(int i=0;i<=M;++i)tax[i]=0;
for(int i=1;i<=N;++i)tax[rak[i]]++;
for(int i=1;i<=M;++i)tax[i]+=tax[i-1];
for(int i=N;i>=1;--i)sa[ tax[ rak[ tp[i]]]-- ]=tp[i];
}
inline void Suffix_Sort(){
M=75;
for(int i=1;i<=N;++i)rak[i]=s[i]-'0'+1,tp[i]=i;
Bucket_Sort();
for(int w=1,p;p<N;M=p,w<<=1){
p=0;
for(int i=1;i<=w;++i)tp[++p]=N-w+i;
for(int i=1;i<=N;++i)if(sa[i]>w)tp[++p]=sa[i]-w;
Bucket_Sort();
swap(tp,rak);
rak[sa[1]]=p=1;
for(int i=2;i<=N;++i)
rak[sa[i]]=(tp[sa[i-1]]==tp[sa[i]] && tp[sa[i-1]+w]==tp[sa[i]+w])?p:++p;
}
for(int i=1;i<=N;++i)printf("%d ",sa[i]);
}
int main(){
scanf("%s",s+1);
N=strlen(s+1);
Suffix_Sort();
return 0;
}
*后缀自动机
【代码实现】
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#define ll long long
using namespace std;
const int N=2010000;
char s[N];
int fa[N],ch[N][26],len[N],siz[N];
int lst=1,node=1,l,t[N],A[N];
ll ans;
void Extend(int c)
{
/*
2+2+2+3行，那么多while但是复杂度是O(n)
*/
int f=lst,p=++node;lst=p;
len[p]=len[f]+1;siz[p]=1;
/*
f为以c结尾的前缀的倒数第二个节点，p为倒数第一个（新建）
len[i] 表示i节点的longest，不用记录shortest（概念在hihocoder后缀自动机1上讲得十分详细）
siz[i]表示以i所代表的endpos的集合元素大小，即所对应的字符串集出现的次数
不用担心复制后的siz，在parent树上复制后的点的siz是它所有儿子siz之和，比1多
*/
while(f&&!ch[f][c]) ch[f][c]=p,f=fa[f];
if(!f) {fa[p]=1;return;}
/*
把前面的一段没有c儿子的节点的c儿子指向p
Situation 1 如果跳到最前面的根的时候，那么把p的parent树上的父亲置为1
*/
int x=ch[f][c],y=++node;
if(len[f]+1==len[x]) {fa[p]=x;node--;return;}
/*
x表示从p一直跳parent树得到的第一个有c儿子的节点的c儿子
Situation 2 如果节点x表示的endpos所对应的字符串集合只有一个字符串，那么把p的parent树父亲设置为x
Situation 2 和 Situation 3 本质不同！！！与机房dalao们讨论两天才知道Situation 2 必须特判的原因！！！详见上方链接的博客
*/
len[y]=len[f]+1; fa[y]=fa[x]; fa[x]=fa[p]=y;
memcpy(ch[y],ch[x],sizeof(ch[y]));
while(f&&ch[f][c]==x) ch[f][c]=y,f=fa[f];
/*
Situation 3 否则把x点复制一遍（parent树父亲、儿子），同时len要更新
（注意len[x]!=len[f]+1,因为通过加点会使x父亲改变）
然后把x点和p点的父亲指向复制点y，再将前面所有本连x的点连向y
*/
}
int main()
{
//Part 1 建立后缀自动机
scanf("%s",s); l=strlen(s);
for(int i=l;i>=1;i--) s[i]=s[i-1];s[0]=0;
for(int i=1;i<=l;i++) Extend(s[i]-'a');
//Part 2 按len从大到小排序（和SA好像啊）后计算答案
for(int i=1;i<=node;i++) t[len[i]]++;
for(int i=1;i<=node;i++) t[i]+=t[i-1];
for(int i=1;i<=node;i++) A[t[len[i]]--]=i;
for(int i=node;i>=1;i--)
{//从小到大枚举，实际上在模拟parent树的DFS
int now=A[i];siz[fa[now]]+=siz[now];
if(siz[now]>1) ans=max(ans,1ll*siz[now]*len[now]);
}
printf("%lldn",ans);
return 0;
}
AC自动机
【简介】
在计算机科学中， A h o – C o r a s i c k Aho–Corasick Aho–Corasick算法是由 A l f r e d V . A h o Alfred V. Aho AlfredV.Aho和 M a r g a r e t J . C o r a s i c k Margaret J.Corasick MargaretJ.Corasick 发明的字符串搜索算法，用于在输入的一串字符串中匹配有限组“字典”中的子串 。它与普通字符串匹配的不同点在于同时与所有字典串进行匹配。算法均摊情况下具有近似于线性的时间复杂度，约为字符串的长度加所有匹配的数量。然而由于需要找到所有匹配数，如果每个子串互相匹配（如字典为 a ， a a ， a a a ， a a a a a，aa，aaa，aaaa a，aa，aaa，aaaa，输入的字符串为 a a a a aaaa aaaa），算法的时间复杂度会近似于匹配的二次函数。
【代码实现】
//https://www.luogu.org/problem/P3796
#include<iostream>
#include<cstdio>
#include<ctype.h>
#include<queue>
#include<cstring>
using namespace std;
inline int read(){
int x=0,f=0;char ch=getchar();
while(!isdigit(ch))f|=ch=='-',ch=getchar();
while(isdigit(ch))x=x*10+(ch^48),ch=getchar();
return f?-x:x;
}
int trie[10501][26],v[10501],cnt;
int fail[10501],ans[151][2];
char s[1000001],ss[151][71];
inline void De(int x){
for(int i=0;i<26;++i)trie[x][i]=0;
fail[x]=v[x]=0;
}
inline void insert(char s[],int id){
int rt=0,len=strlen(s);
for(int i=0;i<len;++i){
int x=s[i]-'a';
if(!trie[rt][x])trie[rt][x]=++cnt,De(cnt);
rt=trie[rt][x];
}
v[rt]=id;
}
inline void AC(){
queue<int> q;
for(int i=0;i<26;++i)if(trie[0][i])q.push(trie[0][i]);
while(!q.empty()){
int x=q.front();q.pop();
for(int i=0;i<26;++i){
if(trie[x][i])fail[trie[x][i]]=trie[fail[x]][i],q.push(trie[x][i]);
else trie[x][i]=trie[fail[x]][i];
}
}
}
inline void solve(char s[]){
int rt=0,len=strlen(s);
for(int i=0;i<len;++i){
int x=s[i]-'a';
rt=trie[rt][x];
for(int j=rt;j;j=fail[j])ans[v[j]][0]++;
}
}
int main(){
int n=read();
while(n){
cnt=0;De(0);
for(int i=1;i<=n;++i){
scanf("%s",ss[i]);
ans[i][1]=i,ans[i][0]=0,insert(ss[i],i);
}
AC();scanf("%s",s),solve(s);
int maxn=0;
for(int i=1;i<=n;++i)if(ans[i][0]>maxn)maxn=ans[i][0];
printf("%dn",maxn);
for(int i=1;i<=n;++i)if(ans[i][0]==maxn)cout<<ss[ans[i][1]]<<"n";
n=read();
}
return 0;
}
高精度计算
高精度加法
【代码实现】
//problemID:https://www.luogu.org/problemnew/show/P1601
#include<iostream>
#include<string>
#include<cstring>
using namespace std;
int a[1007],b[1007];
void Read(int a[]){
string s;
cin>>s;
a[0]=s.length();
for(int i=1;i<=a[0];i++) a[i]=s[a[0]-i]-'0';
}
void Add(int a[],int b[]){
int x=0,i=0,c=max(a[0],b[0]);
while(i<=c){
a[++i]+=b[i]+x;
x=a[i]/10;
a[i]%=10;
}
for(i=c+1;i>0;i--)if(a[i])a[0]=i;break;}
if(i==0)a[0]=1;
}
void Write(int a[]){
for(int i=a[0];i>=1;--i)cout<<a[i];
}
int main(){
Read(a);
Read(b);
Add(a,b);
Write(a);
return 0;
}
复杂度 Θ ( l e n 1 + l e n 2 ) Theta(len1+len2) Θ(len1+len2)
高精度减法
【代码实现】
//problemID:https://www.luogu.org/problemnew/show/P2142
#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;
char a[100007],b[100007];
int c[100007],d[100007],h[100007],f=0,l=0;
int main(){
cin>>a>>b;
int n1=strlen(a),n2=strlen(b);
for(int i=0;i<n1/2;++i)swap(a[i],a[n1-1-i]);
for(int i=0;i<n2/2;++i)swap(b[i],b[n2-1-i]);
for(int i=0;i<n1;++i)c[i]=a[i]-'0';
for(int i=0;i<n2;++i)d[i]=b[i]-'0';
if(n2>n1){
for(int i=0;i<n2;++i) swap(c[i],d[i]);
f=1;
}
if(n1>n2)swap(n1,n2);
for(int i=0;i<n2;++i)h[i]=c[i]-d[i];
for(int i=0;i<n2;++i)if(h[i]<0)h[i]+=10,h[i+1]--;
if(f)cout<<"-";
for(int i=n2-1;i>=0;i--){
if(!l && h[i]){
l=1;
cout<<h[i];
continue;
}
if(l!=0)cout<<h[i];
}
return 0;
}
复杂度 Θ ( l e n 1 + l e n 2 ) Theta(len1+len2) Θ(len1+len2)
高精度乘法
高精度乘单精度
【代码实现】
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int L=100007;
int na[L];
string mul(string a,int b){
string ans;
int La=a.size();
fill(na,na+L,0);
for(int i=La-1;i>=0;i--) na[La-i-1]=a[i]-'0';
int w=0;
for(int i=0;i<La;i++) na[i]=na[i]*b+w,w=na[i]/10,na[i]=na[i]%10;
while(w) na[La++]=w%10,w/=10;
La--;
while(La>=0) ans+=na[La--]+'0';
return ans;
}
int main(){
string a;
int b;
while(cin>>a>>b)cout<<mul(a,b)<<endl;
return 0;
}
复杂度 Θ ( l e n ) Theta(len) Θ(len)
高精度乘高精度
朴素模拟
//problemID:https://www.luogu.org/problem/P1303
#include<iostream>
#include<string>
#include<cstring>
using namespace std;
int a[10007],b[10007],c[10007];
void Read(int a[]){
string s;
cin>>s;
a[0]=s.length();
for(int i=1;i<=a[0];++i)a[i]=s[a[0]-i]-'0';
}
void Add(int a[],int b[]){
int i,x;
for(i=1;i<=a[0];++i){
x=0;
for(int j=1;j<=b[0];++j){
c[i+j-1]+=a[i]*b[j]+x;
x=c[i+j-1]/10;
c[i+j-1]%=10;
}
c[i+b[0]]+=x;
}
c[0]=a[0]+b[0]+1;
while(!c[c[0]] && c[0]>1)c[0]--;
}
void Write(int c[]){
for(int i=c[0];i>=1;--i)cout<<c[i];
}
int main() {
Read(a),Read(b);
Add(a,b),Write(c);
return 0;
}
复杂度 Θ ( l e n 1 ∗ l e n 2 ) Theta(len1*len2) Θ(len1∗len2)
*FFT实现
//https://www.luogu.org/problem/P3803
#include<iostream>
#include<cstdio>
#include<ctype.h>
#include<cmath>
using namespace std;
const double PI=3.1415926535897932384626433238795028841971693993751058209749445923078164062862089986280348253421170679821480865132823066;
inline int read(){
int x=0,f=0;char ch=getchar();
while(!isdigit(ch))f|=ch=='-',ch=getchar();
while(isdigit(ch))x=x*10+(ch^48),ch=getchar();
return f?-x:x;
}
struct complex{
double x,y;
complex(double _x=0,double _y=0){x=_x,y=_y;}
}a[2097152+7],b[2097152+7];
complex operator + (complex a,complex b){return complex(a.x+b.x,a.y+b.y);}
complex operator - (complex a,complex b){return complex(a.x-b.x,a.y-b.y);}
complex operator * (complex a,complex b){return complex(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);}
int l,limit=1,r[2097152+7];
inline void FFT(complex A[],int type){
for(int i=0;i<limit;++i)if(i<r[i])swap(A[i],A[r[i]]);
for(int mid=1;mid<limit;mid<<=1){
double tmp=PI/mid;
complex Wn(cos(tmp),type*sin(tmp));
for(int R=mid<<1,j=0;j<limit;j+=R){
complex w(1,0);
for(int k=0;k<mid;++k,w=w*Wn){
int o=j+k;
complex x=A[o],y=w*A[o+mid];
A[o]=x+y,A[o+mid]=x-y;
}
}
}
}
int main(){
int n=read(),m=read();
for(int i=0;i<=n;++i)a[i].x=read();
for(int i=0;i<=m;++i)b[i].x=read();
while(limit<=n+m)limit<<=1,++l;
for(int i=0;i<limit;++i)r[i]=(r[i>>1]>>1 | ((i&1)<<l-1));
FFT(a,1);FFT(b,1);
for(int i=0;i<limit;++i)a[i]=a[i]*b[i];
FFT(a,-1);
for(int i=0;i<=n+m;++i)printf("%d ",int(a[i].x/limit+0.5));
return 0;
}
复杂度 Θ ( l e n 1 ∗ l o g Theta(len1*log Θ(len1∗log l e n 2 ) len2) len2)
高精度除法
高精度除单精度
【代码实现】
#include<iostream>
#include<algorithm>
using namespace std;
string div(string a,int b){
string r,ans;
int d=0;
if(a=="0") return a;//特判
for(int i=0;i<a.size();++i){
r+=(d*10+a[i]-'0')/b+'0';
d=(d*10+(a[i]-'0'))%b;
}
int p=0;
for(int i=0;i<r.size();++i)if(r[i]!='0'){p=i;break;}
return r.substr(p);
}
int main(){
string a;
int b;
while(cin>>a>>b)cout<<div(a,b)<<endl;
return 0;
}
复杂度 Θ ( l e n ) Theta(len) Θ(len)
高精度除高精度
【代码实现】
#include <iostream>
#include <cstring>
#define ref(i,x,y) for (int i=x; i<=y; i++)
#define def(i,x,y) for (int i=x; i>=y; i--)
#define chstr(a,x,lenx) lenx=strlen(a);ref(i,1,lenx)x[i]=a[lenx-i]-48
#define tl(f) t[f][0]
using namespace std;
char a[501],b[501];
int x[501],y[501],ans[501],t[10][501],lenx,leny;
int main(){
cin>>a>>b;
chstr(a,x,lenx);
chstr(b,y,leny);
tl(1)=leny;
ref(i,1,leny)t[1][i]=y[i];
ref(i,2,9){
tl(i)=tl(i-1);
ref(j,1,tl(i))
t[i][j]=t[i-1][j]+y[j];
ref(j,1,tl(i))if(t[i][j]>9){
t[i][j+1]++;t[i][j]-=10;}
if(t[i][tl(i)+1]!=0)tl(i)++;
}
int lent=lenx,anslen=lenx;
def(i,lenx,1){
int an=0,len1=max(lent-i+1,0);
def(j,9,0){
bool bo=1;
def(k,max(len1,tl(j)),1)
if(t[j][k]>x[i+k-1]){bo=0;break;}
else if(t[j][k]<x[i+k-1])break;
if(bo){an=j;break;}
}
ans[i]=an;
ref(j,1,tl(an))x[j+i-1]-=t[an][j];
ref(j,i,i+tl(an)-1)if(x[j]<0){x[j]+=10;x[j+1]--;}
while(x[lent]==0)lent--;
}
while((ans[anslen]==0)&&(anslen>1))anslen--;
def(i,anslen,1)cout<<ans[i];
return 0;
}
复杂度 Θ ( l e n 1 ∗ l e n 2 ) Theta(len1*len2) Θ(len1∗len2)
*高精度开根
【代码实现】
#include<iostream>
using namespace std;
#define MAX 1001
struct NEW_NUM
{
int num[MAX];
int start;
int end;
NEW_NUM(){
for (int i = 0; i < MAX; i++){
num[i] = 0;
}
}
};
void calculate(NEW_NUM &temp);
void add(NEW_NUM &temp, int num);
void sub(NEW_NUM &a, int a_start, int a_end, NEW_NUM b, int b_start, int b_end);
bool comp(NEW_NUM a, int a_start, int a_end, NEW_NUM b, int b_start, int b_end);
int main(){
char ch[MAX];
NEW_NUM a, b;
cin >> ch;
int i;
a.start = 1;
for (i = 0; i <= MAX-1; i++){
if (ch[i] == ' ')break;
a.num[a.start+i] = ch[i] - '0';
}
a.end = i;
int xx, yy;
xx = yy = 1;
b.start = 1;
if (a.end % 2 == 0){
int te = a.num[xx] * 10 + a.num[xx + 1];
for (int i = 0; i <= 10; i++){
if (i*i > te){
b.num[yy] = i - 1;
a.num[xx + 1] += a.num[xx]*10-(i-1)*(i-1);
a.num[xx] = 0;
if (a.num[xx + 1]>= 10){
a.num[xx] += a.num[xx + 1] / 10;
a.num[xx+1] = a.num[xx+1] % 10;
}
yy++;
break;
}
}
xx = xx + 2;
}
else{
int te = a.num[xx];
for (int i = 0; i <= 10; i++){
if (i*i > te){
b.num[yy] = i - 1;
a.num[xx] -= (i-1)*(i-1);
yy++;
break;
}
}
xx = xx + 1;
}
b.end = 1;
while (xx+1<=a.end){
NEW_NUM temp;
temp.start = 3;
for (int i = 1; i < yy; i++){
temp.num[temp.start+i-1] = b.num[i];
}
b.num[yy] = 0;
b.end = yy;
temp.end = temp.start+yy-1;
calculate(temp);
for (int i = 1; i < 10; i++){
if (i == 1)add(temp, 1);
else add(temp, 2);
if (comp(a, a.start, xx+1, temp, temp.start, temp.end)){
sub(a, a.start, xx+1, temp, temp.start, temp.end);
b.num[yy]++;
}
else{
break;
}
}
yy++;
xx += 2;
}
for (int i = b.start; i <= b.end; i++){
cout << b.num[i];
}
cout << endl;
return 0;
}
bool comp(NEW_NUM a, int a_start,int a_end, NEW_NUM b, int b_start,int b_end){
int i = a_start;
while (a.num[i] == 0)i++;
a.start = i;
int j = b_start;
while (b.num[j] == 0)j++;
if (a_end - i>b_end - j)return true;
if (a_end - i < b_end - j) return false;
int k = 0;
while (k <= a_end - i){
if (a.num[k + i] > b.num[k + j]) return true;
if (a.num[k + i] < b.num[k + j]) return false;
k++;
}
return true;
}
void sub(NEW_NUM &a, int a_start, int a_end, NEW_NUM b, int b_start, int b_end){
int i = a_end;
int j = b_end;
while (j >= b_start){
if (a.num[i] >= b.num[j]) a.num[i] -= b.num[j];
else{
a.num[i - 1]--;
a.num[i] = 10 + a.num[i] - b.num[j];
}
i--;
j--;
}
}
void add(NEW_NUM &temp, int num){
temp.num[temp.end] += num;
int i = temp.end;
while (temp.num[i]>=10){
temp.num[i - 1] += temp.num[i] / 10;
temp.num[i] = temp.num[i] % 10;
i--;
}
if (i < temp.start) temp.start = i;
}
void calculate(NEW_NUM &temp){ //temp*2*i
for (int i = temp.end; i >= temp.start; i--){
temp.num[i] = 2 * temp.num[i];
}
for (int i = temp.end; i >= temp.start; i--){
if (temp.num[i] >= 10){
temp.num[i - 1] += temp.num[i] / 10;
temp.num[i] = temp.num[i] % 10;
}
}
int i = 0;
while (temp.num[i] == 0){
i++;
}
temp.start = i;
}
*高精度取模
【代码实现】
#include<bits/stdc++.h>
using namespace std;
int a[9999],b[9999],c[9999],ans[9999];
void read(int *x) {
string s;
cin>>s;
x[0]=s.length();
for(int i=1; i<=x[0]; i++)
x[i]=s[i-1]-48;
reverse(x+1,x+x[0]+1);
}
void print(int *x) {
for(int i=x[0]; i>=1; i--)
cout<<x[i];
cout<<endl;
}
bool pd() {
if(c[0]>b[0])return 1;
if(c[0]<b[0])return 0;
for(int i=c[0]; i>=1; i--) {
if(c[i]>b[i])return 1;
if(c[i]<b[i])return 0;
}
return 1;
}
void js() {
int d=0;
for(int i=1; i<=c[0]; i++) {
c[i]-=b[i]+d;
if(c[i]<0) {
c[i]+=10;
d=1;
} else d=0;
}
while(c[0]>1&&!c[c[0]])c[0]--;
}
int main() {
read(a);
read(b);
c[0]=0;
for(int i=a[0]; i>=1; i--) {
for(int j=c[0]; j>=1; j--)c[j+1]=c[j];
c[1]=a[i];
c[0]++;
// print(c);
while(pd()) {
js();
ans[i]++;
}
}
ans[0]=a[0];
while(ans[0]>1&&!ans[ans[0]])ans[0]--;
print(c);
return 0;
}
*高精度求小数幂次
【代码实现】
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1300; //100000^250有1250位
int pt;
struct Bign{
int s[MAXN], len;
Bign(int num = 0){
memset(s, 0, sizeof(s));
len = 1;
s[1] = num;
}
Bign operator * (int b)const{
Bign c;
c.len = len + 10;
for (int i = 1; i <= c.len; i++){
c.s[i] += s[i] * b;
c.s[i+1] = c.s[i] / 10;
c.s[i] %= 10;
}
c.clean();
return c;
}
void clean(){
while (len > 1 && !s[len]) len--;
}
};
ostream& operator << (ostream &out, const Bign &x){
int i;
for (i = x.len; i > 0 && i > pt; i--) //输出整数部分
out << x.s[i];
if (i){ //若i不为0，表示还有小数部分
out << "."; //先输出"."
for (i = pt; i > 0; i--) //再输出小数部分
out << x.s[i];
}
return out;
}
int main(){
double a;
int n;
while (cin >> a >> n){
//求a的小数位数
pt = 0; //pt记录a的小数位数
while (fabs(a - round(a)) > 1e-6){ //若a不等于a的整数部分，表示a不是整数
pt++; //小数位数加一位
a *= 10;
}
pt *= n; //a^n的小数位数等于a的小数位数 ×n
//求s = a ^ n
Bign s = 1;
for (int i = 1; i <= n; i++)
s = s * (int)round(a);
cout << s << endl;
}
return 0;
}
高精大合集
原版
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
using namespace std;
#define DIGIT 4 //四位隔开,即万进制
#define DEPTH 10000 //万进制
#define MAXX 1000+5 //题目最大位数/4，要不大直接设为最大位数也行
typedef int bignum_t[MAXX+1];
/************************************************************************/
/* 读取操作数，对操作数进行处理存储在数组里 */
/************************************************************************/
int read(bignum_t a,istream&is=cin)
{
char buf[MAXX*DIGIT+1],ch ;
int i,j ;
memset((void*)a,0,sizeof(bignum_t));
if(!(is>>buf)) return 0;
for(a[0]=strlen(buf),i=a[0]/2-1; i>=0; i--)
ch=buf[i],buf[i]=buf[a[0]-1-i],buf[a[0]-1-i]=ch ;
for(a[0]=(a[0]+DIGIT-1)/DIGIT,j=strlen(buf); j<a[0]*DIGIT; buf[j++]='0');
for(i=1; i<=a[0]; i++)
for(a[i]=0,j=0; j<DIGIT; j++)
a[i]=a[i]*10+buf[i*DIGIT-1-j]-'0';
for(; !a[a[0]]&&a[0]>1; a[0]--);
return 1 ;
}
void write(const bignum_t a,ostream&os=cout)
{
int i,j ;
for(os<<a[i=a[0]],i--;i;i--)
for(j=DEPTH/10;j;j/=10)
os<<a[i]/j%10;
}
int comp(const bignum_t a,const bignum_t b)
{
int i ;
if(a[0]!=b[0])
return a[0]-b[0];
for(i=a[0]; i; i--)
if(a[i]!=b[i])
return a[i]-b[i];
return 0 ;
}
int comp(const bignum_t a,const int b)
{
int c[12]=
{
1
}
;
for(c[1]=b; c[c[0]]>=DEPTH; c[c[0]+1]=c[c[0]]/DEPTH,c[c[0]]%=DEPTH,c[0]++);
return comp(a,c);
}
int comp(const bignum_t a,const int c,const int d,const bignum_t b)
{
int i,t=0,O=-DEPTH*2 ;
if(b[0]-a[0]<d&&c)
return 1 ;
for(i=b[0]; i>d; i--)
{
t=t*DEPTH+a[i-d]*c-b[i];
if(t>0)return 1 ;
if(t<O)return 0 ;
}
for(i=d; i; i--)
{
t=t*DEPTH-b[i];
if(t>0)return 1 ;
if(t<O)return 0 ;
}
return t>0 ;
}
/************************************************************************/
/* 大数与大数相加 */
/************************************************************************/
void add(bignum_t a,const bignum_t b)
{
int i ;
for(i=1; i<=b[0]; i++)
if((a[i]+=b[i])>=DEPTH)
a[i]-=DEPTH,a[i+1]++;
if(b[0]>=a[0])
a[0]=b[0];
else
for(; a[i]>=DEPTH&&i<a[0]; a[i]-=DEPTH,i++,a[i]++);
a[0]+=(a[a[0]+1]>0);
}
/************************************************************************/
/* 大数与小数相加 */
/************************************************************************/
void add(bignum_t a,const int b)
{
int i=1 ;
for(a[1]+=b; a[i]>=DEPTH&&i<a[0]; a[i+1]+=a[i]/DEPTH,a[i]%=DEPTH,i++);
for(; a[a[0]]>=DEPTH; a[a[0]+1]=a[a[0]]/DEPTH,a[a[0]]%=DEPTH,a[0]++);
}
/************************************************************************/
/* 大数相减(被减数>=减数) */
/************************************************************************/
void sub(bignum_t a,const bignum_t b)
{
int i ;
for(i=1; i<=b[0]; i++)
if((a[i]-=b[i])<0)
a[i+1]--,a[i]+=DEPTH ;
for(; a[i]<0; a[i]+=DEPTH,i++,a[i]--);
for(; !a[a[0]]&&a[0]>1; a[0]--);
}
/************************************************************************/
/* 大数减去小数(被减数>=减数) */
/************************************************************************/
void sub(bignum_t a,const int b)
{
int i=1 ;
for(a[1]-=b; a[i]<0; a[i+1]+=(a[i]-DEPTH+1)/DEPTH,a[i]-=(a[i]-DEPTH+1)/DEPTH*DEPTH,i++);
for(; !a[a[0]]&&a[0]>1; a[0]--);
}
void sub(bignum_t a,const bignum_t b,const int c,const int d)
{
int i,O=b[0]+d ;
for(i=1+d; i<=O; i++)
if((a[i]-=b[i-d]*c)<0)
a[i+1]+=(a[i]-DEPTH+1)/DEPTH,a[i]-=(a[i]-DEPTH+1)/DEPTH*DEPTH ;
for(; a[i]<0; a[i+1]+=(a[i]-DEPTH+1)/DEPTH,a[i]-=(a[i]-DEPTH+1)/DEPTH*DEPTH,i++);
for(; !a[a[0]]&&a[0]>1; a[0]--);
}
/************************************************************************/
/* 大数相乘，读入被乘数a，乘数b，结果保存在c[] */
/************************************************************************/
void mul(bignum_t c,const bignum_t a,const bignum_t b)
{
int i,j ;
memset((void*)c,0,sizeof(bignum_t));
for(c[0]=a[0]+b[0]-1,i=1; i<=a[0]; i++)
for(j=1; j<=b[0]; j++)
if((c[i+j-1]+=a[i]*b[j])>=DEPTH)
c[i+j]+=c[i+j-1]/DEPTH,c[i+j-1]%=DEPTH ;
for(c[0]+=(c[c[0]+1]>0); !c[c[0]]&&c[0]>1; c[0]--);
}
/************************************************************************/
/* 大数乘以小数，读入被乘数a，乘数b，结果保存在被乘数 */
/************************************************************************/
void mul(bignum_t a,const int b)
{
int i ;
for(a[1]*=b,i=2; i<=a[0]; i++)
{
a[i]*=b ;
if(a[i-1]>=DEPTH)
a[i]+=a[i-1]/DEPTH,a[i-1]%=DEPTH ;
}
for(; a[a[0]]>=DEPTH; a[a[0]+1]=a[a[0]]/DEPTH,a[a[0]]%=DEPTH,a[0]++);
for(; !a[a[0]]&&a[0]>1; a[0]--);
}
void mul(bignum_t b,const bignum_t a,const int c,const int d)
{
int i ;
memset((void*)b,0,sizeof(bignum_t));
for(b[0]=a[0]+d,i=d+1; i<=b[0]; i++)
if((b[i]+=a[i-d]*c)>=DEPTH)
b[i+1]+=b[i]/DEPTH,b[i]%=DEPTH ;
for(; b[b[0]+1]; b[0]++,b[b[0]+1]=b[b[0]]/DEPTH,b[b[0]]%=DEPTH);
for(; !b[b[0]]&&b[0]>1; b[0]--);
}
/**************************************************************************/
/* 大数相除,读入被除数a，除数b，结果保存在c[]数组 */
/* 需要comp()函数 */
/**************************************************************************/
void div(bignum_t c,bignum_t a,const bignum_t b)
{
int h,l,m,i ;
memset((void*)c,0,sizeof(bignum_t));
c[0]=(b[0]<a[0]+1)?(a[0]-b[0]+2):1 ;
for(i=c[0]; i; sub(a,b,c[i]=m,i-1),i--)
for(h=DEPTH-1,l=0,m=(h+l+1)>>1; h>l; m=(h+l+1)>>1)
if(comp(b,m,i-1,a))h=m-1 ;
else l=m ;
for(; !c[c[0]]&&c[0]>1; c[0]--);
c[0]=c[0]>1?c[0]:1 ;
}
void div(bignum_t a,const int b,int&c)
{
int i ;
for(c=0,i=a[0]; i; c=c*DEPTH+a[i],a[i]=c/b,c%=b,i--);
for(; !a[a[0]]&&a[0]>1; a[0]--);
}
/************************************************************************/
/* 大数平方根，读入大数a，结果保存在b[]数组里 */
/* 需要comp()函数 */
/************************************************************************/
void sqrt(bignum_t b,bignum_t a)
{
int h,l,m,i ;
memset((void*)b,0,sizeof(bignum_t));
for(i=b[0]=(a[0]+1)>>1; i; sub(a,b,m,i-1),b[i]+=m,i--)
for(h=DEPTH-1,l=0,b[i]=m=(h+l+1)>>1; h>l; b[i]=m=(h+l+1)>>1)
if(comp(b,m,i-1,a))h=m-1 ;
else l=m ;
for(; !b[b[0]]&&b[0]>1; b[0]--);
for(i=1; i<=b[0]; b[i++]>>=1);
}
/************************************************************************/
/* 返回大数的长度 */
/************************************************************************/
int length(const bignum_t a)
{
int t,ret ;
for(ret=(a[0]-1)*DIGIT,t=a[a[0]]; t; t/=10,ret++);
return ret>0?ret:1 ;
}
/************************************************************************/
/* 返回指定位置的数字，从低位开始数到第b位，返回b位上的数 */
/************************************************************************/
int digit(const bignum_t a,const int b)
{
int i,ret ;
for(ret=a[(b-1)/DIGIT+1],i=(b-1)%DIGIT; i; ret/=10,i--);
return ret%10 ;
}
/************************************************************************/
/* 返回大数末尾0的个数 */
/************************************************************************/
int zeronum(const bignum_t a)
{
int ret,t ;
for(ret=0; !a[ret+1]; ret++);
for(t=a[ret+1],ret*=DIGIT; !(t%10); t/=10,ret++);
return ret ;
}
void comp(int*a,const int l,const int h,const int d)
{
int i,j,t ;
for(i=l; i<=h; i++)
for(t=i,j=2; t>1; j++)
while(!(t%j))
a[j]+=d,t/=j ;
}
void convert(int*a,const int h,bignum_t b)
{
int i,j,t=1 ;
memset(b,0,sizeof(bignum_t));
for(b[0]=b[1]=1,i=2; i<=h; i++)
if(a[i])
for(j=a[i]; j; t*=i,j--)
if(t*i>DEPTH)
mul(b,t),t=1 ;
mul(b,t);
}
/************************************************************************/
/* 组合数 */
/************************************************************************/
void combination(bignum_t a,int m,int n)
{
int*t=new int[m+1];
memset((void*)t,0,sizeof(int)*(m+1));
comp(t,n+1,m,1);
comp(t,2,m-n,-1);
convert(t,m,a);
delete[]t ;
}
/************************************************************************/
/* 排列数 */
/************************************************************************/
void permutation(bignum_t a,int m,int n)
{
int i,t=1 ;
memset(a,0,sizeof(bignum_t));
a[0]=a[1]=1 ;
for(i=m-n+1; i<=m; t*=i++)
if(t*i>DEPTH)
mul(a,t),t=1 ;
mul(a,t);
}
#define SGN(x) ((x)>0?1:((x)<0?-1:0))
#define ABS(x) ((x)>0?(x):-(x))
int read(bignum_t a,int&sgn,istream&is=cin)
{
char str[MAXX*DIGIT+2],ch,*buf ;
int i,j ;
memset((void*)a,0,sizeof(bignum_t));
if(!(is>>str))return 0 ;
buf=str,sgn=1 ;
if(*buf=='-')sgn=-1,buf++;
for(a[0]=strlen(buf),i=a[0]/2-1; i>=0; i--)
ch=buf[i],buf[i]=buf[a[0]-1-i],buf[a[0]-1-i]=ch ;
for(a[0]=(a[0]+DIGIT-1)/DIGIT,j=strlen(buf); j<a[0]*DIGIT; buf[j++]='0');
for(i=1; i<=a[0]; i++)
for(a[i]=0,j=0; j<DIGIT; j++)
a[i]=a[i]*10+buf[i*DIGIT-1-j]-'0' ;
for(; !a[a[0]]&&a[0]>1; a[0]--);
if(a[0]==1&&!a[1])sgn=0 ;
return 1 ;
}
struct bignum
{
bignum_t num ;
int sgn ;
public :
inline bignum()
{
memset(num,0,sizeof(bignum_t));
num[0]=1 ;
sgn=0 ;
}
inline int operator!()
{
return num[0]==1&&!num[1];
}
inline bignum&operator=(const bignum&a)
{
memcpy(num,a.num,sizeof(bignum_t));
sgn=a.sgn ;
return*this ;
}
inline bignum&operator=(const int a)
{
memset(num,0,sizeof(bignum_t));
num[0]=1 ;
sgn=SGN (a);
add(num,sgn*a);
return*this ;
}
;
inline bignum&operator+=(const bignum&a)
{
if(sgn==a.sgn)add(num,a.num);
else if
(sgn&&a.sgn)
{
int ret=comp(num,a.num);
if(ret>0)sub(num,a.num);
else if(ret<0)
{
bignum_t t ;
memcpy(t,num,sizeof(bignum_t));
memcpy(num,a.num,sizeof(bignum_t));
sub (num,t);
sgn=a.sgn ;
}
else memset(num,0,sizeof(bignum_t)),num[0]=1,sgn=0 ;
}
else if(!sgn)
memcpy(num,a.num,sizeof(bignum_t)),sgn=a.sgn ;
return*this ;
}
inline bignum&operator+=(const int a)
{
if(sgn*a>0)add(num,ABS(a));
else if(sgn&&a)
{
int ret=comp(num,ABS(a));
if(ret>0)sub(num,ABS(a));
else if(ret<0)
{
bignum_t t ;
memcpy(t,num,sizeof(bignum_t));
memset(num,0,sizeof(bignum_t));
num[0]=1 ;
add(num,ABS (a));
sgn=-sgn ;
sub(num,t);
}
else memset(num,0,sizeof(bignum_t)),num[0]=1,sgn=0 ;
}
else if
(!sgn)sgn=SGN(a),add(num,ABS(a));
return*this ;
}
inline bignum operator+(const bignum&a)
{
bignum ret ;
memcpy(ret.num,num,sizeof (bignum_t));
ret.sgn=sgn ;
ret+=a ;
return ret ;
}
inline bignum operator+(const int a)
{
bignum ret ;
memcpy(ret.num,num,sizeof (bignum_t));
ret.sgn=sgn ;
ret+=a ;
return ret ;
}
inline bignum&operator-=(const bignum&a)
{
if(sgn*a.sgn<0)add(num,a.num);
else if
(sgn&&a.sgn)
{
int ret=comp(num,a.num);
if(ret>0)sub(num,a.num);
else if(ret<0)
{
bignum_t t ;
memcpy(t,num,sizeof(bignum_t));
memcpy(num,a.num,sizeof(bignum_t));
sub(num,t);
sgn=-sgn ;
}
else memset(num,0,sizeof(bignum_t)),num[0]=1,sgn=0 ;
}
else if(!sgn)add (num,a.num),sgn=-a.sgn ;
return*this ;
}
inline bignum&operator-=(const int a)
{
if(sgn*a<0)add(num,ABS(a));
else if(sgn&&a)
{
int ret=comp(num,ABS(a));
if(ret>0)sub(num,ABS(a));
else if(ret<0)
{
bignum_t t ;
memcpy(t,num,sizeof(bignum_t));
memset(num,0,sizeof(bignum_t));
num[0]=1 ;
add(num,ABS(a));
sub(num,t);
sgn=-sgn ;
}
else memset(num,0,sizeof(bignum_t)),num[0]=1,sgn=0 ;
}
else if
(!sgn)sgn=-SGN(a),add(num,ABS(a));
return*this ;
}
inline bignum operator-(const bignum&a)
{
bignum ret ;
memcpy(ret.num,num,sizeof(bignum_t));
ret.sgn=sgn ;
ret-=a ;
return ret ;
}
inline bignum operator-(const int a)
{
bignum ret ;
memcpy(ret.num,num,sizeof(bignum_t));
ret.sgn=sgn ;
ret-=a ;
return ret ;
}
inline bignum&operator*=(const bignum&a)
{
bignum_t t ;
mul(t,num,a.num);
memcpy(num,t,sizeof(bignum_t));
sgn*=a.sgn ;
return*this ;
}
inline bignum&operator*=(const int a)
{
mul(num,ABS(a));
sgn*=SGN(a);
return*this ;
}
inline bignum operator*(const bignum&a)
{
bignum ret ;
mul(ret.num,num,a.num);
ret.sgn=sgn*a.sgn ;
return ret ;
}
inline bignum operator*(const int a)
{
bignum ret ;
memcpy(ret.num,num,sizeof (bignum_t));
mul(ret.num,ABS(a));
ret.sgn=sgn*SGN(a);
return ret ;
}
inline bignum&operator/=(const bignum&a)
{
bignum_t t ;
div(t,num,a.num);
memcpy (num,t,sizeof(bignum_t));
sgn=(num[0]==1&&!num[1])?0:sgn*a.sgn ;
return*this ;
}
inline bignum&operator/=(const int a)
{
int t ;
div(num,ABS(a),t);
sgn=(num[0]==1&&!num [1])?0:sgn*SGN(a);
return*this ;
}
inline bignum operator/(const bignum&a)
{
bignum ret ;
bignum_t t ;
memcpy(t,num,sizeof(bignum_t));
div(ret.num,t,a.num);
ret.sgn=(ret.num[0]==1&&!ret.num[1])?0:sgn*a.sgn ;
return ret ;
}
inline bignum operator/(const int a)
{
bignum ret ;
int t ;
memcpy(ret.num,num,sizeof(bignum_t));
div(ret.num,ABS(a),t);
ret.sgn=(ret.num[0]==1&&!ret.num[1])?0:sgn*SGN(a);
return ret ;
}
inline bignum&operator%=(const bignum&a)
{
bignum_t t ;
div(t,num,a.num);
if(num[0]==1&&!num[1])sgn=0 ;
return*this ;
}
inline int operator%=(const int a)
{
int t ;
div(num,ABS(a),t);
memset(num,0,sizeof (bignum_t));
num[0]=1 ;
add(num,t);
return t ;
}
inline bignum operator%(const bignum&a)
{
bignum ret ;
bignum_t t ;
memcpy(ret.num,num,sizeof(bignum_t));
div(t,ret.num,a.num);
ret.sgn=(ret.num[0]==1&&!ret.num [1])?0:sgn ;
return ret ;
}
inline int operator%(const int a)
{
bignum ret ;
int t ;
memcpy(ret.num,num,sizeof(bignum_t));
div(ret.num,ABS(a),t);
memset(ret.num,0,sizeof(bignum_t));
ret.num[0]=1 ;
add(ret.num,t);
return t ;
}
inline bignum&operator++()
{
*this+=1 ;
return*this ;
}
inline bignum&operator--()
{
*this-=1 ;
return*this ;
}
;
inline int operator>(const bignum&a)
{
return sgn>0?(a.sgn>0?comp(num,a.num)>0:1):(sgn<0?(a.sgn<0?comp(num,a.num)<0:0):a.sgn<0);
}
inline int operator>(const int a)
{
return sgn>0?(a>0?comp(num,a)>0:1):(sgn<0?(a<0?comp(num,-a)<0:0):a<0);
}
inline int operator>=(const bignum&a)
{
return sgn>0?(a.sgn>0?comp(num,a.num)>=0:1):(sgn<0?(a.sgn<0?comp(num,a.num)<=0:0):a.sgn<=0);
}
inline int operator>=(const int a)
{
return sgn>0?(a>0?comp(num,a)>=0:1):(sgn<0?(a<0?comp(num,-a)<=0:0):a<=0);
}
inline int operator<(const bignum&a)
{
return sgn<0?(a.sgn<0?comp(num,a.num)>0:1):(sgn>0?(a.sgn>0?comp(num,a.num)<0:0):a.sgn>0);
}
inline int operator<(const int a)
{
return sgn<0?(a<0?comp(num,-a)>0:1):(sgn>0?(a>0?comp(num,a)<0:0):a>0);
}
inline int operator<=(const bignum&a)
{
return sgn<0?(a.sgn<0?comp(num,a.num)>=0:1):(sgn>0?(a.sgn>0?comp(num,a.num)<=0:0):a.sgn>=0);
}
inline int operator<=(const int a)
{
return sgn<0?(a<0?comp(num,-a)>=0:1):
(sgn>0?(a>0?comp(num,a)<=0:0):a>=0);
}
inline int operator==(const bignum&a)
{
return(sgn==a.sgn)?!comp(num,a.num):0 ;
}
inline int operator==(const int a)
{
return(sgn*a>=0)?!comp(num,ABS(a)):0 ;
}
inline int operator!=(const bignum&a)
{
return(sgn==a.sgn)?comp(num,a.num):1 ;
}
inline int operator!=(const int a)
{
return(sgn*a>=0)?comp(num,ABS(a)):1 ;
}
inline int operator[](const int a)
{
return digit(num,a);
}
friend inline istream&operator>>(istream&is,bignum&a)
{
read(a.num,a.sgn,is);
return is ;
}
friend inline ostream&operator<<(ostream&os,const bignum&a)
{
if(a.sgn<0)
os<<'-' ;
write(a.num,os);
return os ;
}
friend inline bignum sqrt(const bignum&a)
{
bignum ret ;
bignum_t t ;
memcpy(t,a.num,sizeof(bignum_t));
sqrt(ret.num,t);
ret.sgn=ret.num[0]!=1||ret.num[1];
return ret ;
}
friend inline bignum sqrt(const bignum&a,bignum&b)
{
bignum ret ;
memcpy(b.num,a.num,sizeof(bignum_t));
sqrt(ret.num,b.num);
ret.sgn=ret.num[0]!=1||ret.num[1];
b.sgn=b.num[0]!=1||ret.num[1];
return ret ;
}
inline int length()
{
return :: length(num);
}
inline int zeronum()
{
return :: zeronum(num);
}
inline bignum C(const int m,const int n)
{
combination(num,m,n);
sgn=1 ;
return*this ;
}
inline bignum P(const int m,const int n)
{
permutation(num,m,n);
sgn=1 ;
return*this ;
}
};
/**+++++++++++++++++++分界线++++++++++++++++++++++**/
bignum ans;
bignum c;
int main()
{
freopen("1.in","r",stdin);
freopen("2.out","w",stdout);
cin>>ans>>c;
cout<<ans*c;
return 0;
}
整理版
#include<iostream>
#include<cstring>
#include<complex>
#define ll long long
using namespace std;
#define DIGIT 4
#define DEPTH 10000
#define MAXX 1000+5
typedef ll bignum_t[MAXX+1];
void write(const bignum_t a,ostream&os=cout){int i,j;for(os<<a[i=a[0]],i--;i;i--)for(j=DEPTH/10;j;j/=10)os<<a[i]/j%10;}
ll comp(const bignum_t a,const bignum_t b){int i;if(a[0]!=b[0])return a[0]-b[0];for(i=a[0];i;i--)if(a[i]!=b[i])return a[i]-b[i];return 0;}
ll comp(const bignum_t a,const ll b){ll c[12]={1};for(c[1]=b;c[c[0]]>=DEPTH;c[c[0]+1]=c[c[0]]/DEPTH,c[c[0]]%=DEPTH,c[0]++);return comp(a,c);}
ll comp(const bignum_t a,const ll c,const ll d,const bignum_t b){ll i,t=0,O=-DEPTH*2;if(b[0]-a[0]<d&&c) return 1;
for(i=b[0];i>d;i--){t=t*DEPTH+a[i-d]*c-b[i];if(t>0)return 1;if(t<O)return 0;}for(i=d;i;i--){t=t*DEPTH-b[i];if(t>0)return 1;if(t<O)return 0;}return t>0;}
void add(bignum_t a,const bignum_t b){ll i;for(i=1;i<=b[0];i++)if((a[i]+=b[i])>=DEPTH)a[i]-=DEPTH,a[i+1]++;if(b[0]>=a[0])a[0]=b[0];else for(;a[i]>=DEPTH&&i<a[0];a[i]-=DEPTH,i++,a[i]++);a[0]+=(a[a[0]+1]>0);}
void add(bignum_t a,const ll b){ll i=1;for(a[1]+=b;a[i]>=DEPTH&&i<a[0];a[i+1]+=a[i]/DEPTH,a[i]%=DEPTH,i++);for(;a[a[0]]>=DEPTH;a[a[0]+1]=a[a[0]]/DEPTH,a[a[0]]%=DEPTH,a[0]++);}
void sub(bignum_t a,const bignum_t b){for(ll i=1;i<=b[0];i++)if((a[i]-=b[i])<0)a[i+1]--,a[i]+=DEPTH ;for(ll i;a[i]<0;a[i]+=DEPTH,i++,a[i]--);for(ll i;!a[a[0]]&&a[0]>1;a[0]--);}
void sub(bignum_t a,const ll b){ll i=1;for(a[1]-=b;a[i]<0;a[i+1]+=(a[i]-DEPTH+1)/DEPTH,a[i]-=(a[i]-DEPTH+1)/DEPTH*DEPTH,i++);for(;!a[a[0]]&&a[0]>1;a[0]--);}
void sub(bignum_t a,const bignum_t b,const ll c,const ll d){ll i,O=b[0]+d;for(i=1+d;i<=O;i++)if((a[i]-=b[i-d]*c)<0)a[i+1]+=(a[i]-DEPTH+1)/DEPTH,a[i]-=(a[i]-DEPTH+1)/DEPTH*DEPTH;
for(;a[i]<0;a[i+1]+=(a[i]-DEPTH+1)/DEPTH,a[i]-=(a[i]-DEPTH+1)/DEPTH*DEPTH,i++);for(;!a[a[0]]&&a[0]>1;a[0]--);}
void mul(bignum_t c,const bignum_t a,const bignum_t b){ll i,j;memset((void*)c,0,sizeof(bignum_t));
for(c[0]=a[0]+b[0]-1,i=1;i<=a[0];i++)for(j=1;j<=b[0];j++)if((c[i+j-1]+=a[i]*b[j])>=DEPTH)c[i+j]+=c[i+j-1]/DEPTH,c[i+j-1]%=DEPTH;for(c[0]+=(c[c[0]+1]>0);!c[c[0]]&&c[0]>1;c[0]--);}
void mul(bignum_t a,const ll b){ll i;for(a[1]*=b,i=2;i<=a[0];i++){a[i]*=b;if(a[i-1]>=DEPTH)a[i]+=a[i-1]/DEPTH,a[i-1]%=DEPTH;}for(;a[a[0]]>=DEPTH;a[a[0]+1]=a[a[0]]/DEPTH,a[a[0]]%=DEPTH,a[0]++);for(;!a[a[0]]&&a[0]>1;a[0]--);}
void mul(bignum_t b,const bignum_t a,const ll c,const ll d){int i;memset((void*)b,0,sizeof(bignum_t));for(b[0]=a[0]+d,i=d+1;i<=b[0];i++)if((b[i]+=a[i-d]*c)>=DEPTH)b[i+1]+=b[i]/DEPTH,b[i]%=DEPTH;
for(;b[b[0]+1];b[0]++,b[b[0]+1]=b[b[0]]/DEPTH,b[b[0]]%=DEPTH);for(;!b[b[0]]&&b[0]>1;b[0]--);}
void div(bignum_t c,bignum_t a,const bignum_t b){ll h,l,m,i;memset((void*)c,0,sizeof(bignum_t));c[0]=(b[0]<a[0]+1)?(a[0]-b[0]+2):1;for(i=c[0];i;sub(a,b,c[i]=m,i-1),i--)for(h=DEPTH-1,l=0,m=(h+l+1)>>1;h>l;m=(h+l+1)>>1)if(comp(b,m,i-1,a))h=m-1;else l=m;
for(;!c[c[0]]&&c[0]>1;c[0]--);c[0]=c[0]>1?c[0]:1;}
void div(bignum_t a,const ll b,ll&c){ll i;for(c=0,i=a[0];i;c=c*DEPTH+a[i],a[i]=c/b,c%=b,i--);for(;!a[a[0]]&&a[0]>1;a[0]--);}
ll length(const bignum_t a){ll t,ret ;for(ret=(a[0]-1)*DIGIT,t=a[a[0]];t;t/=10,ret++);return ret>0?ret:1;}
ll digit(const bignum_t a,const ll b){ll i,ret;for(ret=a[(b-1)/DIGIT+1],i=(b-1)%DIGIT;i;ret/=10,i--);return ret%10;}
#define SGN(x) ((x)>0?1:((x)<0?-1:0))
#define ABS(x) ((x)>0?(x):-(x))
ll read(bignum_t a,ll&sgn,istream&is=cin){char str[MAXX*DIGIT+2],ch,*buf;ll i,j;memset((void*)a,0,sizeof(bignum_t));if(!(is>>str)) return 0;buf=str,sgn=1;if(*buf=='-')sgn=-1,buf++;
for(a[0]=strlen(buf),i=a[0]/2-1;i>=0;i--) ch=buf[i],buf[i]=buf[a[0]-1-i],buf[a[0]-1-i]=ch;for(a[0]=(a[0]+DIGIT-1)/DIGIT,j=strlen(buf);j<a[0]*DIGIT;buf[j++]='0');
for(i=1;i<=a[0];i++)for(a[i]=0,j=0;j<DIGIT;j++) a[i]=a[i]*10+buf[i*DIGIT-1-j]-'0';for(;!a[a[0]]&&a[0]>1;a[0]--);if(a[0]==1&&!a[1]) sgn=0;return 1;}
struct bignum{bignum_t num;ll sgn;
public:
inline bignum(){memset(num,0,sizeof(bignum_t));num[0]=1;sgn=0;}
inline ll operator!(){return num[0]==1&&!num[1];}
inline bignum&operator=(const bignum&a){memcpy(num,a.num,sizeof(bignum_t));sgn=a.sgn ;return *this;}
inline bignum&operator=(const ll a){memset(num,0,sizeof(bignum_t));num[0]=1 ;sgn=SGN (a);add(num,sgn*a);return *this;}
inline bignum&operator+=(const bignum&a){if(sgn==a.sgn)add(num,a.num);else if(sgn&&a.sgn){ll ret=comp(num,a.num);if(ret>0)sub(num,a.num);
else if(ret<0){bignum_t t ;memcpy(t,num,sizeof(bignum_t));memcpy(num,a.num,sizeof(bignum_t));sub(num,t);sgn=a.sgn;}else memset(num,0,sizeof(bignum_t)),num[0]=1,sgn=0;
}else if(!sgn)memcpy(num,a.num,sizeof(bignum_t)),sgn=a.sgn;return *this;}
inline bignum&operator+=(const ll a){if(sgn*a>0) add(num,ABS(a));else if(sgn&&a){ll ret=comp(num,ABS(a));if(ret>0)sub(num,ABS(a));
else if(ret<0){bignum_t t;memcpy(t,num,sizeof(bignum_t));memset(num,0,sizeof(bignum_t));num[0]=1;add(num,ABS(a));sgn=-sgn;sub(num,t);}else memset(num,0,sizeof(bignum_t)),num[0]=1,sgn=0;
}else if(!sgn)sgn=SGN(a),add(num,ABS(a));return *this;}
inline bignum operator+(const bignum&a){bignum ret;memcpy(ret.num,num,sizeof(bignum_t));ret.sgn=sgn;ret+=a;return ret;}
inline bignum operator+(const ll a){bignum ret;memcpy(ret.num,num,sizeof(bignum_t));ret.sgn=sgn;ret+=a;return ret;}
inline bignum&operator-=(const bignum&a){if(sgn*a.sgn<0)add(num,a.num);else if(sgn&&a.sgn){ll ret=comp(num,a.num);if(ret>0) sub(num,a.num);
else if(ret<0){bignum_t t;memcpy(t,num,sizeof(bignum_t));memcpy(num,a.num,sizeof(bignum_t));sub(num,t);sgn=-sgn;}else memset(num,0,sizeof(bignum_t)),num[0]=1,sgn=0;
}else if(!sgn)add(num,a.num),sgn=-a.sgn;return *this;}
inline bignum&operator-=(const ll a){if(sgn*a<0)add(num,ABS(a));else if(sgn&&a){ll ret=comp(num,ABS(a));if(ret>0)sub(num,ABS(a));
else if(ret<0){bignum_t t;memcpy(t,num,sizeof(bignum_t));memset(num,0,sizeof(bignum_t));num[0]=1;add(num,ABS(a));sub(num,t);sgn=-sgn;}else memset(num,0,sizeof(bignum_t)),num[0]=1,sgn=0;
}else if(!sgn)sgn=-SGN(a),add(num,ABS(a));return *this;}
inline bignum operator-(const bignum&a){bignum ret;memcpy(ret.num,num,sizeof(bignum_t));ret.sgn=sgn;ret-=a;return ret;}
inline bignum operator-(const ll a){bignum ret;memcpy(ret.num,num,sizeof(bignum_t));ret.sgn=sgn;ret-=a;return ret;}
inline bignum&operator*=(const bignum&a){bignum_t t;mul(t,num,a.num);memcpy(num,t,sizeof(bignum_t));sgn*=a.sgn;return*this;}
inline bignum&operator*=(const ll a){mul(num,ABS(a));sgn*=SGN(a);return*this;}
inline bignum operator*(const bignum&a){bignum ret;mul(ret.num,num,a.num);ret.sgn=sgn*a.sgn;return ret;}
inline bignum operator*(const ll a){bignum ret;memcpy(ret.num,num,sizeof (bignum_t));mul(ret.num,ABS(a));ret.sgn=sgn*SGN(a);return ret;}
inline bignum&operator/=(const bignum&a){bignum_t t;div(t,num,a.num);memcpy (num,t,sizeof(bignum_t));sgn=(num[0]==1&&!num[1])?0:sgn*a.sgn ;return*this;}
inline bignum&operator/=(const ll a){ll t;div(num,ABS(a),t);sgn=(num[0]==1&&!num [1])?0:sgn*SGN(a);return*this;}
inline bignum operator/(const bignum&a){bignum ret;bignum_t t;memcpy(t,num,sizeof(bignum_t));div(ret.num,t,a.num);ret.sgn=(ret.num[0]==1&&!ret.num[1])?0:sgn*a.sgn;return ret;}
inline bignum operator/(const ll a){bignum ret;ll t;memcpy(ret.num,num,sizeof(bignum_t));div(ret.num,ABS(a),t);ret.sgn=(ret.num[0]==1&&!ret.num[1])?0:sgn*SGN(a);return ret;}
inline bignum&operator%=(const bignum&a){bignum_t t;div(t,num,a.num);if(num[0]==1&&!num[1])sgn=0;return*this;}
inline ll operator%=(const ll a){ll t;div(num,ABS(a),t);memset(num,0,sizeof(bignum_t));num[0]=1;add(num,t);return t;}
inline bignum operator%(const bignum&a){bignum ret;bignum_t t;memcpy(ret.num,num,sizeof(bignum_t));div(t,ret.num,a.num);ret.sgn=(ret.num[0]==1&&!ret.num[1])?0:sgn;return ret;}
inline ll operator%(const ll a){bignum ret;ll t;memcpy(ret.num,num,sizeof(bignum_t));div(ret.num,ABS(a),t);memset(ret.num,0,sizeof(bignum_t));ret.num[0]=1;add(ret.num,t);return t;}
inline bignum&operator++(){*this+=1 ;return*this;}inline bignum&operator--(){*this-=1 ;return*this;}
inline ll operator>(const bignum&a){return sgn>0?(a.sgn>0?comp(num,a.num)>0:1):(sgn<0?(a.sgn<0?comp(num,a.num)<0:0):a.sgn<0);}
inline ll operator>(const ll a){return sgn>0?(a>0?comp(num,a)>0:1):(sgn<0?(a<0?comp(num,-a)<0:0):a<0);}
inline ll operator>=(const bignum&a){return sgn>0?(a.sgn>0?comp(num,a.num)>=0:1):(sgn<0?(a.sgn<0?comp(num,a.num)<=0:0):a.sgn<=0);}
inline ll operator>=(const ll a){return sgn>0?(a>0?comp(num,a)>=0:1):(sgn<0?(a<0?comp(num,-a)<=0:0):a<=0);}
inline ll operator<(const bignum&a){return sgn<0?(a.sgn<0?comp(num,a.num)>0:1):(sgn>0?(a.sgn>0?comp(num,a.num)<0:0):a.sgn>0);}
inline ll operator<(const ll a){return sgn<0?(a<0?comp(num,-a)>0:1):(sgn>0?(a>0?comp(num,a)<0:0):a>0);}
inline ll operator<=(const bignum&a){return sgn<0?(a.sgn<0?comp(num,a.num)>=0:1):(sgn>0?(a.sgn>0?comp(num,a.num)<=0:0):a.sgn>=0);}
inline ll operator<=(const ll a){return sgn<0?(a<0?comp(num,-a)>=0:1):(sgn>0?(a>0?comp(num,a)<=0:0):a>=0);}
inline ll operator==(const bignum&a){return(sgn==a.sgn)?!comp(num,a.num):0;}
inline ll operator==(const ll a){return(sgn*a>=0)?!comp(num,ABS(a)):0;}
inline ll operator!=(const bignum&a){return(sgn==a.sgn)?comp(num,a.num):1;}
inline ll operator!=(const ll a){return(sgn*a>=0)?comp(num,ABS(a)):1;}
inline ll operator[](const ll a){return digit(num,a);}
friend inline istream&operator>>(istream&is,bignum&a){read(a.num,a.sgn,is);return is;}
friend inline ostream&operator<<(ostream&os,const bignum&a){if(a.sgn<0)os<<'-';write(a.num,os);return os;}
inline ll length(){return ::length(num);}
};
const int mod1=19260817,mod2=1e9+7,mod3=777777773;bignum a,n;ll y,x;
bignum fpow(bignum a,bignum b){bignum ans;ans=1;while(b!=0){if(b%2==1) ans=ans*a;a=a*a;b=b/2;}return ans;}
ll pow1(ll a,ll b){ll ans=1;while(b){if(b&1) ans=ans*a%mod1;a=a*a%mod1;b>>=1;}return ans;}
ll pow2(ll a,ll b){ll ans=1;while(b){if(b&1) ans=ans*a%mod2;a=a*a%mod2;b>>=1;}return ans;}
ll pow3(ll a,ll b){ll ans=1;while(b){if(b&1) ans=ans*a%mod3;a=a*a%mod3;b>>=1;}return ans;}
ll ppow(ll a,ll b){ll ans=1;while(b){if(b&1) ans=ans*a;a=a*a;b>>=1;}return ans;}
int main(){
cin>>n;a=2;y=2;
if(n<=1e4){cout<<fpow(a,n)+n*2-1;return 0;}
if(n<=1e6){int l=0;for(int i=n.length();i>0;i--) x+=(ll)n[i]*ppow(10,n.length()-l++-1);cout<<(pow1(2,x)+x*2-1)%mod1;return 0;}
if(n<=1e10){ll l=0;for(ll i=n.length();i>0;i--) x+=(ll)n[i]*ppow(10,n.length()-l++-1);cout<<(pow2(2,x)+x*2-1)%mod2;return 0;}
if(n<=1e18){ll l=0;for(ll i=n.length();i>0;i--) x+=(ll)n[i]*ppow(10,n.length()-l++-1);cout<<(pow3(2,x)+x*2-1)%mod3;return 0;}
}
最后
以上就是清脆绿茶为你收集整理的模板库(七) - 字符串算法字符串算法的全部内容，希望文章能够帮你解决模板库(七) - 字符串算法字符串算法所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复