【快速幂+高精度】SSL 2314 穿越丛林

丛林"/>

【快速幂+高精度】SSL 2314 穿越丛林

大意

给定若干个数字，求出 28的个数 2 8 的 个 数 $2^{8的个数}$

思路

由于数据 50000 50000 $50000$。。。
于是，暴模炸掉，高精炸掉，压位高精 TLE T L E $TLE$

所以，选择了快速幂+压位高精200 ms m s $ms$

代码

#include<cstdio>
#include<vector>
#define ymw 1000000000//压位高精度
using namespace std;int n,k=0;
vector<long long>ans,x;
char c;
inline int read()
{int f=0;while(c=getchar(),c<48||c>57);f=(f<<3)+(f<<1)+c-48;while(c=getchar(),c>47&&c<58) f=(f<<3)+(f<<1)+c-48;return f;
}
inline void write(long long x){if(x>9)write(x/10);putchar(x%10+48);return;}
inline void mulx()//ans*x
{vector<long long>c;for(register int i=0;i<ans.size();i++)for(register int j=0;j<x.size();j++){if(c.size()==i+j) c.push_back(ans[i]*x[j]);else c[i+j]+=ans[i]*x[j];if(c.size()==i+j+1) c.push_back(c[i+j]/ymw);else c[i+j+1]+=c[i+j]/ymw;c[i+j]%=ymw;}ans=c;while(!ans.back()) ans.pop_back();return;
}
inline void self()//x*x
{vector<long long>c;for(register int i=0;i<x.size();i++)for(register int j=0;j<x.size();j++){if(c.size()==i+j) c.push_back(x[i]*x[j]);else c[i+j]+=x[i]*x[j];if(c.size()==i+j+1) c.push_back(c[i+j]/ymw);else c[i+j+1]+=c[i+j]/ymw;c[i+j]%=ymw;}x=c;while(!x.back()) x.pop_back();return;
}
inline void ksm(register int y)//快速幂
{while(y){if(y&1) mulx();self();y>>=1;}return;
}
signed main()
{n=read();for(register int i=0;i<n;i++) if(read()==8) k++;ans.push_back(1);x.push_back(2);ksm(k);for(register int i=ans.size()-1;i>=0;i--)//输出{long long k=ymw/10;if(i<ans.size()-1)while(k>ans[i]&&k>1) putchar(48),k/=10;write(ans[i]);}
}