BZOJ5300 [Cqoi2018]九连环【dp + 高精】-白红宇

BZOJ5300 [Cqoi2018]九连环【dp + 高精】

阅读量：4648 次

发布时间：2019-06-09

本文共 1869 字，大约阅读时间需要 6 分钟。

题目链接

题解

这题真的是很丧病，，卡高精卡到哭

我们设\(f[i]\)表示卸掉前\(i\)个环需要的步数

那么

\[f[i] = 2*f[i - 2] + f[i - 1] + 1\]

直接高精递推不仅\(MLE\)而且\(TLE\)

然后就要用到数学求通项公式，~~或者打表找规律~~

\[f[n] = \lfloor \frac{2^{n + 1}}{3} \rfloor\]

高精乘低精就可以过了

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         #define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)#define REP(i,n) for (int i = 1; i <= (n); i++)#define mp(a,b) make_pair
          
           (a,b)#define cls(s) memset(s,0,sizeof(s))#define cp pair
           
            #define LL long long intusing namespace std;const int maxn = 100005,B = 100000000,maxm = 100005,INF = 1000000000;inline int read(){ int out = 0,flag = 1; char c = getchar(); while (c < 48 || c > 57){if (c == '-') flag = -1; c = getchar();} while (c >= 48 && c <= 57){out = (out << 3) + (out << 1) + c - 48; c = getchar();} return out * flag;}struct NUM{ LL s[100000],len; NUM(){cls(s); len = 0;} void out(){ if (!len){putchar('0'); return;} printf("%lld",s[len - 1]); for (int i = len - 2; i >= 0; i--) printf("%08lld",s[i]); }}F;inline void operator *=(NUM& a,const int& b){ LL tmp,carry = 0; for (int i = 0; i < a.len; i++){ tmp = 1ll * a.s[i] * b + carry; a.s[i] = tmp % B; carry = tmp / B; } while (carry) a.s[a.len++] = carry % B,carry /= B;}inline NUM operator /(const NUM& a,const int& b){ NUM c; c.len = a.len; LL tmp,carry = 0; for (int i = a.len - 1; i >= 0; i--){ tmp = a.s[i] + 1ll * carry * B; if (tmp < b) c.s[i] = 0,carry = tmp; else c.s[i] = tmp / b,carry = tmp % b; } //if (carry) c = c + 1; while (c.len && !c.s[c.len - 1]) c.len--; return c;}int main(){ int T = read(); while (T--){ int n = read() + 1,bin = 1 << 30; F.len = 1; F.s[0] = 1; int tmp = n / 30,t = n % 30; while (tmp--) F *= bin; while (t--) F *= 2; F = F / 3; F.out(); puts(""); } return 0;}