2656: [Zjoi2012]数列(sequence)（递归+高精度）

　　好久没写题了T T NOIP 期中考双血崩

　　显然f(x)=f(x>>1)+f((x>>1)+1)，考虑每次往x>>1递归，求出f(x)，复杂度O(logN)

　　我们设f(x>>1)的值为ansa[x]，f((x>>1)+1)的值为ansb[x]

　　如果x>>1为偶数，ansa[x]=ansa[x>>1]，ansb[x]=ansa[x>>1]+ansb[x>>1]

　　如果x>>1为奇数，ansa[x]=ansa[x>>1]+ansb[x>>1]，ansb[x]=ansb[x>>1]

　　随便举个例子很好理解的，高精度写起来比较麻烦T T

#include<iostream> #include<cstring> #include<cstdlib> #include<cstdio> #include<algorithm> #define ll long long using namespace std; const int base=1e9, bit=9; int T; char s[110]; void read(int &k) {int f=1;k=0;char c=getchar();while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar();while(c<='9'&&c>='0')k=k*10+c-'0',c=getchar();k*=f; } struct tjmll {int sum[110], f; tjmll(){f=0; memset(sum, 0, sizeof(sum));}tjmll operator= (ll x){memset(sum, 0, sizeof(sum));while(x){sum[++sum[0]]=x%base;x/=base;}return *this;} } ansa, ansb, n; void print(const tjmll &a) {if(a.f==-1) putchar('-');printf("%d", a.sum[a.sum[0]]);for(int i=a.sum[0]-1;i>=1;i--) printf("%0*d", bit, a.sum[i]); } tjmll operator+(const tjmll &a, const tjmll &b) {tjmll tmp; tmp.sum[0]=max(a.sum[0], b.sum[0]);for(int i=1;i<=tmp.sum[0];i++) {tmp.sum[i]+=a.sum[i]+b.sum[i];tmp.sum[i+1]+=tmp.sum[i]/base;tmp.sum[i]%=base;}if(tmp.sum[tmp.sum[0]+1]) tmp.sum[0]++;return tmp; } inline void div2(tjmll &x) {int pre=0;for(int i=x.sum[0];i;i--){int tmp=pre*base+x.sum[i];x.sum[i]=tmp>>1;pre=tmp&1;}if(!x.sum[x.sum[0]]) x.sum[0]--; } inline void dfs(tjmll x) {if(x.sum[0]==0) return;if(x.sum[0]==1 && x.sum[1]==1) ansa=0, ansb=1;tjmll now; now=now+x;div2(x); dfs(x);if(now.sum[1]&1) ansa=ansa+ansb;else ansb=ansa+ansb; } int main() {read(T);while(T--){scanf("%s", s+1); n=0; int len=strlen(s+1), now=0;for(int i=len;i;i--){if((len-i)%bit==0) ++n.sum[0], now=1;n.sum[n.sum[0]]+=(s[i]-'0')*now; now*=10;}ansa=0; ansb=0; dfs(n); print(ansa); puts("");}return 0; } View Code

 

转载于:https://www.cnblogs.com/Sakits/p/7881512.html

总结

以上是生活随笔为你收集整理的2656: [Zjoi2012]数列(sequence)（递归+高精度）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。