bzoj 3907 网格 bzoj2822 [AHOI2012]树屋阶梯——卡特兰数(阶乘高精度模板)

时间:2023-02-12 19:56:43

题目:https://www.lydsy.com/JudgeOnline/problem.php?id=3907

   https://www.lydsy.com/JudgeOnline/problem.php?id=2822

学到了阶乘高精度的板子。用起来好爽……

https://www.cnblogs.com/Tunix/p/4354348.html

#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;
const ll mod=1e8;const int N=1e5+;
int n,m,x[N],v[N],p[N],tot;
ll a[N],b[N];
ll pw(ll x,int k)
{
ll ret=;while(k){if(k&)ret*=x;x*=x;k>>=;}return ret;
}
void mul(ll a[],ll b)// a[] is already an iterator
{
ll &l=a[],x=;
for(int i=;i<=l;i++)
{
a[i]=a[i]*b+x;
x=a[i]/mod;a[i]%=mod;
}
while(x)a[++l]=x%mod,x/=mod;
}
void getc(ll a[],int n,int m)
{
memset(x,,sizeof x);
for(int i=;i<=n;i++)x[i]++;
for(int i=;i<=m;i++)x[i]--;
for(int i=;i<=n-m;i++)x[i]--;
for(int i=n;i>=;i--)
if(!v[i])mul(a,pw(i,x[i]));
else x[v[i]]+=x[i],x[i/v[i]]+=x[i];//+=x[i]!!!
}
void dec(ll a[],ll b[])
{
ll &l=a[];
for(int i=;i<=l;i++)
{
if(a[i]<b[i])a[i+]--,a[i]+=mod;
a[i]-=b[i];
}
while(!a[l])l--;
}
void print(ll a[])
{
int l=a[];
printf("%lld",a[l]);
for(int i=l-;i;i--)printf("%08lld",a[i]);
printf("\n");
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=n+m;i++)
{
if(!v[i])p[++tot]=i;
for(int j=,k;j<=tot&&(k=p[j]*i)<=n+m;j++)
{
v[k]=p[j];if(i%p[j]==)break;
}
}
a[]=a[]=b[]=b[]=;
getc(a,n+m,m);
getc(b,n+m,n+);
dec(a,b);
print(a);
return ;
}
#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;
const ll mod=1e8;const int N=1e5+;
int n,m,x[N],v[N],p[N],tot;
ll a[N],b[N];
ll pw(ll x,int k)
{
ll ret=;while(k){if(k&)ret*=x;x*=x;k>>=;}return ret;
}
void mul(ll a[],ll b)// a[] is already an iterator
{
ll &l=a[],x=;
for(int i=;i<=l;i++)
{
a[i]=a[i]*b+x;
x=a[i]/mod;a[i]%=mod;
}
while(x)a[++l]=x%mod,x/=mod;
}
void getc(ll a[],int n,int m)
{
memset(x,,sizeof x);
for(int i=;i<=n;i++)x[i]++;
for(int i=;i<=m;i++)x[i]--;
for(int i=;i<=n-m;i++)x[i]--;
for(int i=n;i>=;i--)
if(!v[i])mul(a,pw(i,x[i]));
else x[v[i]]+=x[i],x[i/v[i]]+=x[i];//+=x[i]!!!
}
void dec(ll a[],ll b[])
{
ll &l=a[];
for(int i=;i<=l;i++)
{
if(a[i]<b[i])a[i+]--,a[i]+=mod;
a[i]-=b[i];
}
while(!a[l])l--;
}
void print(ll a[])
{
int l=a[];
printf("%lld",a[l]);
for(int i=l-;i;i--)printf("%08lld",a[i]);
printf("\n");
}
int main()
{
scanf("%d",&n);m=n;
for(int i=;i<=n+m;i++)
{
if(!v[i])p[++tot]=i;
for(int j=,k;j<=tot&&(k=p[j]*i)<=n+m;j++)
{
v[k]=p[j];if(i%p[j]==)break;
}
}
a[]=a[]=b[]=b[]=;
getc(a,n+m,m);
getc(b,n+m,n+);
dec(a,b);
print(a);
return ;
}

稍稍修改后的第二题代码