mcfx's blog - 高精度

mcfx's blog - 高精度 2016-10-21T00:08:00+08:00 Typecho /feed/atom/category/gjd/ <![CDATA[BZOJ 2656: [Zjoi2012]数列(sequence)]]> /archives/57/ 2016-10-21T00:08:00+08:00 2016-10-21T00:08:00+08:00 admin

###Description
小白和小蓝在一起上数学课，下课后老师留了一道作业，求下面这个数列的通项公式：
![1.jpg][1]
小白作为一个数学爱好者，很快就计算出了这个数列的通项公式。于是，小白告诉小蓝自己已经做出来了，但为了防止小蓝抄作业，小白并不想把公式公布出来。于是小白为了向小蓝证明自己的确做出来了此题以达到其炫耀的目的，想出了一个绝妙的方法：即让小蓝说一个正整数N，小白则说出 的值，如果当N很大时小白仍能很快的说出正确答案，这就说明小白的确得到了公式。但这个方法有一个很大的漏洞：小蓝自己不会做，没法验证小白的答案是否正确。作为小蓝的好友，你能帮帮小蓝吗？

###Input
输入文件第一行有且只有一个正整数T，表示测试数据的组数。
第2～T+1行，每行一个非负整数N。

###Output
输出文件共包含T行。
第i行应包含一个不含多余前缀0的数，它的值应等于An(n为输入数据中第i+1行被读入的整数)

###Sample Input
3
1
3
10

###Sample Output
1
2
3

###HINT
T<=20,N<=10^100

###Solution
首先手推几个较小的值，可以发现当i为奇数时，递归算几次A(i)，会产生一些相同的值
那么直接记忆化就行了
至于证明，我也不会（从二进制的角度考虑的话，似乎大概就logn种值）

###Code
```c++
#include<cstdio>
#include<cstring>
#include<tr1/unordered_map>

#define bas 1000000000
#define rep(a,b) if(a<(b))a=(b)

struct hjd
{
	int a[20],len;
	hjd(){
		len=0;
		memset(a,0,sizeof(a));
	}
	hjd(const hjd &x)
	{
		len=x.len;
		memset(a,0,sizeof(a));
		for(int i=0;i<len;i++)a[i]=x.a[i];
	}
	hjd(int x){
		len=1;
		memset(a,0,sizeof(a));
		a[0]=x;
	}
	bool operator ==(const hjd &x)const
	{
		if(len^x.len)return 0;
		for(int i=0;i<len;i++)
			if(a[i]^x.a[i])return 0;
		return 1;
	}
	inline void div2()
	{
		for(int i=len-1;i>0;i--)
		{
			if(a[i]&1)a[i-1]+=bas;
			a[i]>>=1;
		}
		a[0]>>=1;
		if(!a[len-1])len--;
	}
	inline void plus(const hjd &x)
	{
		rep(len,x.len);
		for(int i=0;i<len;i++)
		{
			a[i]+=x.a[i];
			if(a[i]>bas)a[i]-=bas,a[i+1]++;
		}
		if(a[len])len++;
	}
	inline void print()
	{
		printf("%d",a[len-1]);
		for(int i=len-2;i>=0;i--)
			printf("%09d",a[i]);
		printf("\n");
	}
};

struct hjd_hash
{
	size_t operator ()(const hjd &x)const//乱搞哈希 
	{
		int ans=0;
		for(int i=0;i<x.len;i++)
			ans^=x.a[i];
		return ans;
	}
};

std::tr1::unordered_map<hjd,hjd,hjd_hash> s;
int aaa=0;
hjd calc(hjd x)
{
	hjd ret;
	if(!x.len)return ret;
	while((~x.a[0]&1)&&(x.len!=1||x.a[0]!=1))x.div2();//除去2 
	if(s.find(x)!=s.end())return s[x];//记忆化 
	hjd y=x;
	x.div2();
	ret=calc(x);
	x.plus(1);
	ret.plus(calc(x));//计算A(x) 
	s[y]=ret;
	return ret;
}

char buf[200];

int main()
{
	s[1]=1;
	int T,n,uu[9],y=1;
	for(int i=0;i<9;i++)
		uu[i]=y,y*=10;
	scanf("%d",&T);
	while(T--)
	{
		s.clear();
		s[1]=1;
		scanf("%s",buf);
		n=strlen(buf);
		hjd tmp;
		for(int i=n-1,j=0,ll=1;i>=0;i--)//输入，倒序 
		{
			tmp.len=ll;
			tmp.a[ll-1]+=(buf[i]-'0')*uu[j];
			j++;
			if(j==9)j=0,ll++;
		}
		hjd t2=calc(tmp);
		if(!t2.len)
			printf("0\n");
		else
		{
			t2.print();
		}
	}
}
```

[1]: /usr/uploads/2016/10/1978638953.jpg

]]> <![CDATA[BZOJ 1265: [AHOI2006]斐波卡契的兔子]]> /archives/24/ 2016-09-13T22:36:00+08:00 2016-09-13T22:36:00+08:00 admin

###Description
卡卡开始养兔子了！妈妈给他买了一对刚出生的兔子，卡卡了解到兔子的繁殖规律是这样的：才出生的一对兔子在一个月后将第一次生出一胎a对兔子，接着在出生后的二个月又将生出b对兔子，在第三个月和以后每个月都会繁殖c对兔子。(a <= b <= c) 由斐波纳契数列我们知道兔子的繁殖速度是很快的，然而卡卡有兔子一样多的好朋友，卡卡想在m个月后有k对兔子，以便分给他们的好友，他的愿望是否能够实现呢？ 
[任务] 编写一个程序：从输入文件中读入输入信息；计算m个月后卡卡将有多少对兔子，设之为P；计算如果m个月后卡卡要拥有至少k对兔子，那么开始时妈妈至少应该为卡卡购买多少对兔子，设之为Q；将结果输出至输出文件。

###Input
输入文件的第一行有4个正整数：a, b, c和m；而第二行则仅含一个正整数k。它们的含义见上文描述。

###Output
你的程序将向输出文件输出两行，第一行是一个整数P而第二行是一个整数Q。

###Sample Input
0 1 1 10
10000

###Sample Output
89
113

###HINT
0 <= a <= b <= c <= 100, 1 <= m <= 3 000, 1 <= k <= 10^6000

###Solution
我们用x,y,z表示一个月、两个月、三个月及以上的兔子，那么每次x=ax+by+cz,y=x,z=y+z就可以求出p，而q就是k/p向上取整
k/p可以用p,2p,4p,...,(2^t)p去求
然而为什么AC的人这么少呢。。

###Code
```c++
#include<bits/stdc++.h>
  
#define gm 1000
#define cas 10000000
#define max2 20050
  
int a[gm],b[gm],c[gm],k[gm],m,al,bl,cl,kl,t[gm],aa,bb,cc,r1[gm],r2[gm],r3[gm],l1,l2,l3;
int f[max2][gm],fl[max2],tf[max2][gm],tfl[max2],ans[gm],ansl,rrt[gm];
char tmp[10000];
  
inline void print(int *x,int xl)
{
    printf("%d",x[xl-1]);
    for(int i=xl-2;i>=0;i--)printf("%07d",x[i]);
}
  
inline int max(int a,int b)
{
    if(a>b)return a;else return b;
}
  
inline void add(int *x,int *y,int &xl,int yl)
{
    int ll=max(xl,yl);
    for(int i=0;i<ll;i++)
    {
        x[i]+=y[i];
        if(x[i]>=cas)x[i]-=cas,x[i+1]++;
    }
    if(x[ll])xl=ll+1;else xl=ll;
}
  
inline void addto(int *x,int *y,int *z,int xl,int yl,int &zl)
{
    zl=max(xl,yl);
    z[0]=0;
    for(int i=0;i<zl;i++)
    {
        z[i]+=x[i]+y[i];
        if(z[i]>=cas)z[i]-=cas,z[i+1]=1;else z[i+1]=0;
    }
    if(z[zl])zl++;
}
 
inline void multo(int *x,int y,int *z,int xl,int &zl)
{
    z[0]=0;
    for(int i=0;i<xl;i++)
    {
        z[i]+=x[i]*y;
        z[i+1]=z[i]/cas;
        z[i]%=cas;
    }
    if(z[xl])zl=xl+1;else zl=xl;
}
  
inline bool larger(int *x,int *y,int xl,int yl)
{
    if(xl>yl)return true;
    if(xl<yl)return false;
    for(int i=max(xl,yl)-1;i>=0;i--)
    {
        if(x[i]>y[i])return true;
        if(x[i]<y[i])return false;
    }
    return false;
}
  
inline void dec(int *x,int *y,int &xl,int yl)
{
    for(int i=0;i<xl;i++)
    {
        x[i]-=y[i];
        while(x[i]<0)x[i]+=cas,x[i+1]--;
    }
    while(xl&&!x[xl-1])xl--;
}
  
int main()
{
    al=1,bl=0,cl=0;
    a[0]=1;
    scanf("%d%d%d%d",&aa,&bb,&cc,&m);
    scanf("%s",tmp);
    int tml=strlen(tmp),tmp2=1;
    std::reverse(tmp,tmp+tml);
    kl=(tml+6)/7;
    for(int i=0;i<tml;i++)
    {
        if(i%7==0)tmp2=1;
        k[i/7]=k[i/7]+(tmp[i]-'0')*tmp2;
        tmp2*=10;
    }
    for(int i=0;i<m;i++)
    {
        multo(a,aa,r1,al,l1);
        multo(b,bb,r2,bl,l2);
        multo(c,cc,r3,cl,l3);
        add(c,b,cl,bl);
        memcpy(b,a,al*4);
        bl=al;
        addto(r1,r2,a,l1,l2,al);
        add(a,r3,al,l3);
    }
    add(a,b,al,bl);
    add(a,c,al,cl);
    print(a,al);
    printf("\n");
    memcpy(f[0],a,al*4);
    fl[0]=al;
    tf[0][0]=1;
    tfl[0]=1;
    ansl=0;
    int ma;
    for(ma=0;!larger(f[ma],k,fl[ma],kl);ma++)
    {
        multo(f[ma],2,f[ma+1],fl[ma],fl[ma+1]);
        multo(tf[ma],2,tf[ma+1],tfl[ma],tfl[ma+1]);
    }
    for(int i=ma-1;i>=0;i--)
    {
        if(!larger(f[i],k,fl[i],kl))
        {
            dec(k,f[i],kl,fl[i]);
            add(ans,tf[i],ansl,tfl[i]);
        }
    }
    if(kl)
    {
        rrt[0]=1;
        add(ans,rrt,ansl,1);
    }
    print(ans,ansl);
    printf("\n");
    return 0;
}
```

]]> <![CDATA[BZOJ 1089: [SCOI2003]严格n元树]]> /archives/17/ 2016-09-08T22:30:00+08:00 2016-09-08T22:30:00+08:00 admin

###Description
如果一棵树的所有非叶节点都恰好有n个儿子，那么我们称它为严格n元树。如果该树中最底层的节点深度为d
（根的深度为0），那么我们称它为一棵深度为d的严格n元树。例如，深度为2的严格2元树有三个，如下图：
![1.jpg][1]
给出n, d，编程数出深度为d的n元树数目。

###Input
仅包含两个整数n, d(0 < n <= 32, 0 <= d <= 16)

###Output
仅包含一个数，即深度为d的n元树的数目。

###Sample Input
【样例输入1】
2 2

【样例输入2】
2 3

【样例输入3】
3 5

###Sample Output
【样例输出1】
3

【样例输出2】
21

【样例输出2】
58871587162270592645034001

###Solution
我们用f(d)表示深度不大于d的n元树数目，则答案为f(d)-f(d-1)
当深度为d时，可以看做一棵深度为1的n元树，每个叶子节点向下都有d(n-1)种可能，再加上深度为0的情况，可得出f(d)=f(d-1)^n+1

###Code
```c++
#include<cstdio>
#include<memory.h>
#include<cstring>

#define maxnum 100
#define cas 1000000000

int a[maxnum],b[maxnum],t[maxnum],al=1,bl;

inline void mul()
{
	memset(t,0,(al+bl+1)*4);
	for(int i=0;i<al;i++)
		for(int j=0;j<bl;j++)
		{
			long long f=(long long)a[i]*b[j];
			t[i+j]+=f%cas;
			if(t[i+j]>=cas)t[i+j]-=cas,t[i+j+1]++;
			t[i+j+1]+=f/cas;
			if(t[i+j+1]>=cas)t[i+j+1]-=cas,t[i+j+2]++;
		}
	if(t[al+bl-1])al=al+bl;else al=al+bl-1;
	memcpy(a,t,al*4);
}

inline void print(int *a)
{
	printf("%d",a[al-1]);for(int i=al-2;i>=0;i--)printf("%09d",a[i]);printf("\n");
}

int main()
{
	int n,d;
	scanf("%d%d",&n,&d);
	a[0]=1;
	while(d--)
	{
		memcpy(b,a,al*4);
		bl=al;
		for(int i=1;i<n;i++)mul();
		a[0]++;
		for(int i=0;a[i]>=cas;i++)a[i]-=cas,a[i+1]++;
		if(a[al])al++;
	}
	for(int i=0;i<bl;i++)a[i]-=b[i];
	for(int i=0;i<al;i++)if(a[i]<0)a[i]+=cas,a[i+1]--;
	if(!a[al-1])al--;
	print(a);
	printf("\n");
	return 0;
}
```

[1]: /usr/uploads/2016/09/1813884886.jpg

]]> <![CDATA[BZOJ 1002: [FJOI2007]轮状病毒]]> /archives/3/ 2016-09-07T23:02:00+08:00 2016-09-07T23:02:00+08:00 admin

###Description
轮状病毒有很多变种，所有轮状病毒的变种都是从一个轮状基产生的。一个N轮状基由圆环上N个不同的基原子和圆心处一个核原子构成的，2个原子之间的边表示这2个原子之间的信息通道。如下图所示
![bzoj1002.p1.png][1]
N轮状病毒的产生规律是在一个N轮状基中删去若干条边，使得各原子之间有唯一的信息通道，例如共有16个不同的3轮状病毒，如下图所示
![bzoj1002.p2.png][2]
现给定n(N<=100)，编程计算有多少个不同的n轮状病毒

###Input
第一行有1个正整数n

###Output
计算出的不同的n轮状病毒数输出

###Sample Input
3

###Sample Output
16

###Solution
这道题的正解是基尔霍夫矩阵，推出f[i]=f[i-1]*3-f[i-2]+2，然而我这等蒟蒻肯定是不知道怎么证的
下面是我的做法：
首先去掉外面的某条边，图就变成了类似于这样的结构：
![bzoj1002-1.png][3]
可行解就类似于下图：
![bzoj1002-2.png][4]
我们将未与中心节点相连的点标0，相连的标1，删去的边也标1，每个解就变成了一个01串
假设某个解最外面一共去掉k条边，那么这个01串长度为n+k-1，共有2k-1个1，而由于向上的边与删去的边交替出现，每个解一定与每个01串一一对应，所以最外层去掉k条边时，解的个数为 $$C(n+k-1,k\cdot 2-1)$$。
由于固定了某条边必须去掉，这里只求出了总情况数了k/n，所以还需要乘上n/k，最后的结果就是这样的：
$$\sum_k^n C(n+k-1,k\cdot 2-1)\cdot\frac{n}{k}$$
考虑到高精度大约要O(n)，时间复杂度O(n^3)
记录上一个 $$C(n+k-1,k\cdot 2-1)$$，可以优化到O(n^2)

<del>然而这种数据范围为什么不打表。。</del>

###Code
```c++
#include<cstdio>
 
#define cas 10000000
#define maxnum 100
 
int x[maxnum],y[maxnum],tmp[maxnum+1];
 
inline void mul(int a)
{
    tmp[0]=0;
    for(int i=0;i<maxnum;i++)
    {
        y[i]*=a;
        y[i]+=tmp[i];
        tmp[i+1]=y[i]/cas;
        y[i]%=cas;
    }
}
 
inline void div(int a)
{
    for(int i=maxnum-1;i>=0;i--)
    {
        if(i)y[i-1]+=y[i]%a*cas;
        y[i]/=a;
    }
}
 
inline void c(int a,int b)
{
    if(b>a/2)b=a-b;
    for(int i=0;i<maxnum;i++)y[i]=0;
    y[0]=1;
    for(int i=a;i>a-b;i--)mul(i);
    for(int i=2;i<=b;i++)div(i);
}
 
inline void print(int *k)
{
    bool is0=true;
    for(int i=maxnum-1;i>=0;i--)
    {
        if(is0&&k[i])
        {
            is0=false;
            printf("%d",k[i]);
        }
        else if(!is0)
        {
            printf("%07d",k[i]);
        }
    }
}
 
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        c(n+i-1,2*i-1);
        mul(n);
        div(i);
        for(int i=0;i<maxnum;i++)
        {
            x[i]+=y[i];
            if(x[i]>cas)x[i]-=cas,x[i+1]++;
        }
    }
    print(x);
    return 0;
}
```

[1]: /usr/uploads/2016/09/2454961388.png
  [2]: /usr/uploads/2016/09/212298548.png
  [3]: /usr/uploads/2016/09/3955661276.png
  [4]: /usr/uploads/2016/09/3098156740.png
  [5]: /usr/uploads/2016/09/1992184554.gif
  [6]: /usr/uploads/2016/09/1288349390.gif
  [7]: /usr/uploads/2016/09/1992184554.gif

]]>