递推 + 巧 bao 妙 li 的方法

Problem

$n$ 连环方案数，无取模。

Solution

经过半个小时的推导：

111111 -> 110000 -> 010000 -> .... -> 011000 -> 001000 
      f[4]       1            g[4]           1          

得出以下结果：
$$ans_i=f_{i-2}+2^{i-1}$$
$$f_i=2f_{i-1}+[i\%2=0], f_1=1$$

然后就暴力高精度了。会超时呢。于是去学了压位。
用__int128 压了 37 位，就可以很快的过掉了。

// Code by ajcxsu
// Problem: 9 circles

#include<bits/stdc++.h>
#define CLR(x) memset(x, 0, sizeof(x))
using namespace std;

typedef long long ll;
const int p=37;
__int128 car=1;
void llput(__int128 x, int pre=0) {
    char s[40]; int p=0;
    while(x) s[p++]=x%10, x/=10;
    for(int i=1;i<=pre-p;i++) putchar('0');
    for(int i=p-1;i>=0;i--) putchar(s[i]+'0');
}
struct BIGNUM {
    static const int N=1000;
    __int128 nu[N]={0}, len=0;
    void operator = (int x) {
        len=0;
        while(x) nu[len++]=x%car, x/=car;
        if(!len) len++;
    }
    BIGNUM(int x) { *this=x; }
    void add() { 
        nu[0]++;
        if(nu[0]>=car) nu[0]-=car, nu[1]++;
        if(nu[1]>=car) nu[1]-=car, nu[2]++;
        if(len==1 && nu[1]) len++;
        if(len==2 && nu[2]) len++;
    }
    void operator += (BIGNUM b) {
        len=max(len, b.len)+1;
        for(int i=0;i<=len;i++) {
            nu[i]+=b.nu[i];
            if(nu[i]>=car) nu[i+1]++, nu[i]-=car;
        }
        while(!nu[len-1] && len>1) len--;
    }
    void putout() {
        for(int i=len-1;i>=0;i--)
            if(i!=len-1) llput(nu[i], p);
            else llput(nu[i]);
        putchar('\n');
    }
} ;

int main() {
    for(int i=0;i<37;i++) car*=10;
    int n;
    scanf("%d", &n);
    int na;
    while(n--) {
        scanf("%d", &na);
        if(na==1) puts("1");
        else if(na==2) puts("2");
        else {
            BIGNUM a=1, b=2;
            for(int i=2;i<=na-1;i++) {
                b+=b;
                if(i<=na-2) {
                    if(!(i&1)) a+=a;
                    else a+=a, a.add();
                }
            }
            a+=b, a.putout();
        }
    }
    return 0;
}