【高精】【快速幂】穿越丛林（ssl 2314）

丛林（ssl 2314）"/>

【高精】【快速幂】穿越丛林（ssl 2314）

穿越丛林

ssl 2314

题目大意：

求 2 n 2^n 2n

原题：

题目描述：

ljj 是一位富有冒险心又很喜欢研究数学的孩纸，有一天，他到一个丛林冒险，这里的树长有像0、4、6、8、9这样形状的洞，他要想穿过丛林，必须从这些树洞里钻过去。这时他忽然萌生了一个特别的想法，统计穿越丛林道路的条数！现在他已经知道了要经过丛林道路所经过的n棵树的顺序，以及与每棵上的树洞的形状的数字。

输入：

文件第一行一个整数n，表示丛林中有洞的数的棵数。
接下来一行有n 个被空格隔开的数t[i]，表示第i 棵树长得像的数字。

输出：

文件只有一行，为路径条数。

输入样例：

5
0 0 0 6 8

输出样例

2

说明

【样例说明】最后一棵树的树洞长得像8，表示两个树洞，有以下两条路径可以穿越丛林,见下图：

【数据范围】

30%的数据，1<=n<=50;
60%的数据，1<=n<=500;
90%的数据，1<=n<=5000；
100%的数据，1<=n<=50000；
其中： t [ i ] ∈ ( 0 , 4 , 6 , 8 , 9 ) t[i]∈(0,4,6,8,9) t[i]∈(0,4,6,8,9)，即t[i]属于(0,4,6,8,9)中的某个数。

解题思路：

直接乘2？ 错！
高精乘2？ 错！
快速幂高精乘2？ 错！
那答案是？？？
快速幂加压位高精！！！

代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#define xxy 1000000000ll
using namespace std;
int n,e;
long long t,sum,a[4001],c[4001];
void js(long long x)
{if (x==1) {a[1]=2;return;}js(x/2);long long y=(x&1)+1;for (int i=1;i<=1700;i++)for (int j=1;j<=1700;j++)//快速幂{c[i+j-1]+=a[i]*a[j]*y;c[i+j]+=c[i+j-1]/xxy;//压位c[i+j-1]%=xxy;}t=0;for (int i=1;i<=1700;i++){a[i]=c[i]+t;t=a[i]/xxy;a[i]%=xxy;c[i]=0;}
}
int main()
{freopen("123.txt","r",stdin);scanf("%d",&n);for (int i=1;i<=n;i++){scanf("%d",&e);if (e==8) sum++;}if (sum>=1){js(sum);int k=1700;while (a[k]==0&&k>0) k--;printf("%lld",a[k]);for (int i=k-1;i>0;i--)printf("%0*lld",9,a[i]);//补零输出}else printf("1");
}