算法竞赛程序模板
Biginteger大整数加乘模板
#include <bits/stdc++.h>
using namespace std;
struct BigInteger{
const static int MOD = 10000;
const static int DLEN = 4;
int a[600], len;
BigInteger()
{
memset(a, 0, sizeof(a));
len = 1;
}
BigInteger(int v)
{
memset(a, 0, sizeof(a));
len = 0;
do
{
a[len++] = v%MOD;
v /= MOD;
}while(v);
}
BigInteger(const char s[])
{
memset(a, 0, sizeof(a));
int L = strlen(s);
len = L/DLEN;
if(L%DLEN) len++;
int idx = 0;
for(int i = L - 1; i >= 0; i -= DLEN)
{
int t = 0;
int k = i - DLEN + 1;
if(k < 0) k = 0;
for(int j = k;j <= i;j++)
t = t*10 + s[j] - '0';
a[idx++] = t;
}
}
BigInteger operator + (const BigInteger &b) const
{
BigInteger res;
res.len = max(len, b.len);
for(int i = 0; i <= res.len; ++i)
res.a[i] = 0;
for(int i = 0; i < res.len; ++i)
{
res.a[i] += ((i < len)?a[i]:0)+((i < b.len)?b.a[i]:0);
res.a[i+1] += res.a[i]/MOD;
res.a[i] %= MOD;
}
if(res.a[res.len] > 0)res.len++;
return res;
}
BigInteger operator * (const BigInteger &b) const
{
BigInteger res;
for(int i = 0; i < len;i++)
{
int up = 0;
for(int j = 0;j < b.len;j++)
{
int temp = a[i]*b.a[j] + res.a[i+j] + up;
res.a[i+j] = temp%MOD;
up = temp/MOD;
}
if(up != 0)
res.a[i + b.len] = up;
}
res.len = len + b.len;
while(res.a[res.len - 1] == 0 &&res.len > 1)res.len--;
return res;
}
void output()
{
printf("%d",a[len-1]);
for(int i = len-2;i >=0 ;i--)
printf("%04d",a[i]);
printf("\n");
}
};
int main()
{
char s1[] = "1012315431";
char s2[] = "1215564813";
BigInteger bi1(s1);
BigInteger bi2(s2);
BigInteger bi3 = bi1 + bi2;
BigInteger bi4 = bi1*bi2;
bi3.output();
cout<<endl;
bi4.output();
return 0;
}最长上升子序列
#include <bits/stdc++.h>
#define maxn 100005
#define INF 1000000005
using namespace std;
int vis[maxn];
int main()
{
int n;
scanf("%d",&n);
fill(vis,vis+maxn,INF);
for(int i=0;i<n;i++)
{
int A;
scanf("%d",&A);
*lower_bound(vis,vis+n,A)=A;
}
int len=lower_bound(vis,vis+n,INF)-vis;
}线性筛求欧拉函数
#include <bits/stdc++.h>
#define maxn 1005
using namespace std;
int check[maxn];
int prime[maxn];
int tot=0;
int phi[maxn];
int solve(int n)
{
memset(check,0,sizeof(check));
memset(prime,0,sizeof(prime));
memset(phi,0,sizeof(phi));
tot=0;
for(int i=2;i<=n;i++)
{
if(!check[i])
{
prime[tot]=i;
tot++;
phi[i]=i-1;
}
for(int j=0;j<tot&&prime[j]*i<=n;j++)
{
check[i*prime[j]]=1;
phi[i*prime[j]]=phi[i]*(i%prime[j]?prime[j]-1:prime[j]);
if(i%prime[j]==0)break;
}
}
int sum=0;
for(int i=2;i<=n;i++)sum+=phi[i];
return sum;
}
int main()
{
int C,n;
scanf("%d",&C);
for(int i=1;i<=C;i++)
{
scanf("%d",&n);
cout<<i<<" "<<n<<" ";
int ans=0;
ans=solve(n);
ans=3+2*ans;
cout<<ans<<endl;
}
}拓展中国剩余定理+exgcd+快乘
#include <bits/stdc++.h>
#define maxn 1000005
using namespace std;
typedef long long ll;
ll a[maxn],b[maxn];
int n;
ll exgcd(ll a,ll b,ll &x,ll &y)
{
if(b==0){x=1;y=0;return a;}
ll d=exgcd(b,a%b,x,y);
ll z=x;
x=y;
y=z-y*(a/b);
return d;
}
ll mul(ll a,ll b,ll mod)
{
ll res=0;
while(b>0)
{
if(b&1) res=(res+a)%mod;
a=(a+a)%mod;
b>>=1;
}
return res;
}
ll china()
{
ll x,y,k;
ll M=a[1],ans=b[1];
for(int i=2;i<=n;i++)
{
ll k=M,m=a[i];
ll c=((b[i]-ans)%m+m)%m;
ll d=exgcd(k,m,x,y);
ll thea=m/d;
if(c%d!=0)
{
return -1;
}
x=mul(x,c/d,thea);
ans+=x*M;
M*=thea;
ans=(ans%M+M)%M;
}
return (ans%M+M)%M;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%lld %lld",&a[i],&b[i]);
}
ll ans=china();
printf("%lld",ans);
}哈希求后缀数组
#include <bits/stdc++.h>
#define maxn 300005
using namespace std;
unsigned long long f[maxn],p[maxn];
char s[maxn];
int SA[maxn];
int len;
void pre()
{
p[0]=1;
memset(f,0,sizeof(f));
for(int i=1;i<=len;i++)
{
f[i]=f[i-1]*131+(s[i]-'a'+1);
p[i]=p[i-1]*131;
}
}
int getlen(int X,int Y)
{
int x=max(X,Y),y=min(X,Y);
int L=1,R=len-y+1,ans=0;
while(L<=R)
{
int mid=(L+R)/2;
if(mid>=1&&x+mid-1<=len&&y+mid-1<=len&&(f[x+mid-1]-f[x-1]*p[mid]==f[y+mid-1]-f[y-1]*p[mid]))
{
ans=mid;
L=mid+1;
}
else R=mid-1;
}
return ans;
}
bool cmp(int x,int y)
{
int k=getlen(x,y);
return s[x+k]<s[y+k];
}
int main()
{
scanf("%s",s+1);
len=strlen(s+1);
pre();
for(int i=1;i<=len;i++)SA[i]=i;
sort(SA+1,SA+len+1,cmp);
for(int i=1;i<=len;i++)printf("%d ",SA[i]-1);
printf("\n");
for(int i=1;i<=len;i++)
{
if(i==1){printf("0 ");continue;}
int d=getlen(SA[i],SA[i-1]);
printf("%d ",d);
}
}单高精度乘除法
#include <bits/stdc++.h>
using namespace std;
struct imf
{
int x,y;
int sum;
}num[1005];
int cmp(imf a,imf b)
{
return a.sum<b.sum;
}
int one[20000]={0},two[20000]={0},re[20000]={0};
int len=1,t=0,r=0;
void mul(int x)
{
int f=0;
len+=6;
for(int i=0;i<len;i++)
{
int k=one[i]*x+f;
one[i]=k%10;
f=k/10;
}
while(one[len])len--;
}
void cut(int y)
{
for(int i=t;i>=0;i--)
{
if(i>=1)two[i-1]+=((two[i]%y)*10);
two[i]/=y;
}
while(two[t]==0)t--;
}
int check()
{
if(t>r)
{
return 1;
}
else if(t==r)
{
for(int u=r;u>=0;u--)
{
if(two[u]>re[u])
{
return 1;
}
else if(two[u]<re[u])
{
return 0;
}
}
return 0;
}
else if(t<r)
{
return 0;
}
}
int main()
{
int n;
cin>>n;
int a,b;
cin>>a>>b;
for(int i=0;i<n;i++)
{
cin>>num[i].x>>num[i].y;
num[i].sum=num[i].x*num[i].y;
}
sort(num,num+n,cmp);
one[0]=1;
mul(a);
for(int j=0;j<n;j++)
{
memcpy(two,one,sizeof(one));
t=len;
cut(num[j].y);
if(check())
{
memcpy(re,two,sizeof(two));
r=t;
}
mul(num[j].x);
}
for(int i=r;i>=0;i--)
{
cout<<re[i];
}
}埃氏筛区间素数
#include <bits/stdc++.h>
using namespace std;
long long L,R;
int num[50005]={0},prime[50005];
int tot=0;
int re[1000005]={0};
void generator()
{
for(int i=2;i<=50000;i++)
{
if(!num[i])
{
prime[tot]=i;
tot++;
}
for(int j=0;j<tot&&i*prime[j]<=50000;j++)
{
num[i*prime[j]]=1;
if(i%prime[j]==0)break;
}
}
}
int main()
{
cin>>L>>R;
generator();
for(int i=0;i<tot;i++)
{
for(long long j=max(2ll,(L-1)/prime[i]+1)*prime[i];j<=R;j+=prime[i])
{
re[j-L]=1;
}
}
long long ans=0;
for(long long k=L;k<=R;k++)
{
if(!re[k-L])ans++;
}
cout<<ans;
}SPFA算法求负环
#include <bits/stdc++.h>
#define INF 100000000
#define len 505
using namespace std;
struct imf
{
int to,val;
};
int n;
vector<imf>Q[len];
queue<int>G;
int d[len];
int v[len]={0};
int pl[len]={0};
void SPFA()
{
while(!G.empty())G.pop();
int check=0;
G.push(1);
d[1]=0;
pl[1]++;
while(!G.empty())
{
int tmp=G.front();
G.pop();
v[tmp]=0;
for(int i=0;i<Q[tmp].size();i++)
{
int x=Q[tmp][i].to,y=Q[tmp][i].val;
if(d[x]>d[tmp]+y)
{
d[x]=d[tmp]+y;
if(!v[x])
{
G.push(x);
v[x]=1;
pl[x]++;
if(pl[x]>=n)check=1; //每个点入栈次数不能超过n-1次，否则有负环
}
}
if(check)break;
}
if(check)break;
}
if(check)cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
memset(Q,0,sizeof(Q));
memset(v,0,sizeof(v));
memset(pl,0,sizeof(pl));
fill(d,d+len,INF);
int m,w,S,E,T;
scanf("%d %d %d",&n,&m,&w);
for(int i=0;i<m;i++)
{
scanf("%d %d %d",&S,&E,&T);
Q[S].push_back((imf){E,T});
Q[E].push_back((imf){S,T});
}
for(int i=0;i<w;i++)
{
scanf("%d %d %d",&S,&E,&T);
Q[S].push_back((imf){E,-T});
}
SPFA();
}
}Lucas定理+组合数+线性求乘法逆元
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 4e4;
int mod = 999911659;
int n,q,jc[N],jcinv[N],inv[N];
int pow(int a,int b,int p)
{
int res = 1;
for(;b;b >>= 1)
{
if(b&1)res = (LL)res * a % p;
a = (LL)a * a % p;
}
return res;
}
void init(int p)
{
jcinv[0] = jcinv[1] = inv[1] = jc[1] = jc[0] = 1;
for(int i = 2;i <= p;i ++)
{
inv[i]=(LL)(p-p/i)*inv[p%i]%p;
jcinv[i] = jcinv[i-1] * inv[i] % p;
jc[i] =(LL)jc[i-1] * i % p;
}
}
int C(int x,int y,int p)
{
if(y > x)return 0;
return (LL)jc[x]*jcinv[y]*jcinv[x-y]%p;
}
int lucas(int x,int y,int p)
{
if(y == 0)return 1;
return (LL)C(x%p,y%p,p) * lucas(x/p,y/p,p) % p;
}
