九连环

6760: 九连环

时间限制: 1 Sec 内存限制: 128 MB
提交: 642 解决: 104
[提交] [状态] [讨论版] [命题人:admin]

题目描述

九连环是一种源于中国的传统智力游戏。如图所示，九个圆环套在一把“剑”上，并且互相牵连。游戏的目标是把九个圆环从“剑”上卸下。

圆环的装卸需要遵守两个规则。
第一个（最右边）环任何时候都可以装上或卸下。
如果第k个环没有被卸下，且第k个环右边的所有环都被卸下，则第k+1个环（第k个环左边相邻的环）可以任意装上或卸下。
与魔方的千变万化不同，解九连环的最优策略是唯一的。为简单起见，我们以“四连环”为例，演示这一过程。这里用1表示环在“剑”上，0表示环已经卸下。
初始状态为1111，每部的操作如下：
1101（根据规则2，卸下第2个环）
1100（根据规则1，卸下第1个环）
0100（根据规则2，卸下第4个环）
0101（根据规则1，装上第1个环）
0111（根据规则2，装上第2个环）
0110（根据规则1，卸下第1个环）
0010（根据规则2，卸下第3个环）
0011（根据规则1，装上第1个环）
0001（根据规则2，卸下第2个环）
0000（根据规则1，卸下第1个环）
由此可见，卸下“四连环”至少需要10步。随着环数增加，需要的步数也会随之增多。例如卸下九连环，就至少需要341步。
请你计算，有n个环的情况下，按照规则，全部卸下至少需要多少步。

输入

输入第一行为一个整数m ，表示测试点数目。
接下来m行，每行一个整数n。

输出

输出共m行，对应每个测试点的计算结果。

样例输入

样例输出

5
21
341

提示

对于10%的数据，1≤n≤10。
对于30%的数据，1≤n≤30。
对于100%的数据，1≤n≤105,1≤m≤10。

来源/分类

重庆OI2018

思路：通过找规律可知，

n

n

#include <bits/stdc++.h>
#define enter putchar('
')
#define space putchar(' ')
using namespace std;

template <class T>
void read(T &x)
{
    char c;
    bool op=0;
    while(c=getchar(),c<'0'||c>'9')
    {
        if(c=='-')op=1;
    }
    x=c-'0';
    while(c=getchar(),c>='0' && c<='9')
    {
        x=x*10+c-'0';
    }
    if(op==1) x=-x;
}

template <class T>
void write(T x)
{
    if(x < 0) putchar('-'),x=-x;
    if(x >= 10) write(x / 10);
    putchar('0' + x % 10);
}

const int N = 150000;
const double PI = acos(-1);
int T,x;

struct cp
{
    double a,b;
    cp(){}
    cp(double x, double y):a(x),b(y){}
    cp operator + (const cp &obj) const
    {
        return cp(a+obj.a,b+obj.b);
    }
    cp operator - (const cp &obj) const
    {
        return cp(a-obj.a,b-obj.b);
    }
    cp operator * (const cp &obj) const
    {
        return cp(a*obj.a-b*obj.b,a*obj.b+b*obj.a);
    }
}inv[N],omg[N];

void init(int n)
{
    for(int i=0;i<n;i++)
    {
        omg[i]=cp(cos(2*PI/n*i),sin(2*PI/n*i));
        inv[i]=cp(omg[i].a,-omg[i].b);
    }
}

void fft(cp *a,int n,cp *omg)
{
    int lim = 0;
    while((1<<lim)<n) lim++;
    for(int i=0;i<n;i++)
    {
        int t=0;
        for(int j=0;j<lim;j++)
        {
            if(i>>j&1) t|=1<<(lim-j-1);
        }
        if(i<t) swap(a[i],a[t]);
    }
    for(int l=2; l<=n; l<<=1)
    {
        int m=l/2;
        for(cp *p=a; p!=a+n; p+=l)
        {
            for(int i=0; i<m; i++)
            {
                cp t=omg[n/l*i]*p[i+m];
                p[i+m]=p[i]-t;
                p[i]=p[i]+t;
            }
        }
    }
}

struct big
{
    int g[N],len;
    big()
    {
        memset(g,0,sizeof(g));
        len=1;
    }
    big(int x)
    {
        memset(g,0,sizeof(g));
        len=0;
        if(!x)
        {
            len=1;
            return;
        }
        while(x) g[len++]=x%10,x/=10;
    }
    void out()
    {
        for(int i=len-1; i>=0; i--)
        {
            printf("%d",g[i]);
        }
        enter;
    }
    void operator /= (int x)
    {
        int sum=0, newlen=0;
        for(int i=len-1; i>=0; i--)
        {
            sum=sum*10+g[i];
            if(sum<x) g[i]=0;
            else
            {
                if(!newlen) newlen=i+1;
                g[i]=sum/x;
                sum%=x;
            }
        }
        len=max(newlen,1);
    }
    void operator *= (const big &b)
    {
        static cp A[N], B[N];
        int newlen=len+b.len-1,n=1;
        while(n<newlen) n<<=1;
        for(int i=0; i<n; i++)
        {
            A[i]=cp(i<len ? g[i]:0,0);
            B[i]=cp(i<b.len ? b.g[i]:0,0);
        }
        init(n);
        fft(A, n, omg);
        fft(B, n, omg);
        for(int i=0; i<n; i++)
        {
            A[i]=A[i]*B[i];
        }
        fft(A, n, inv);
        for(int i=0; i<newlen; i++)
        {
            g[i]=(int)floor(A[i].a/n+0.5);
        }
        g[len=newlen]=0;
        for(int i=0; i<len; i++)
        {
            g[i+1]+=g[i]/10,g[i]%=10;
        }
        if(g[len]) len++;
    }
}ret,a;

int main()
{

    read(T);
    while(T--)
    {
        read(x),x++;
        ret=big(1),a=big(2);
        while(x)
        {
            if(x&1) ret*=a;
            a*=a;
            x>>=1;
        }
        ret/=3;
        ret.out();
    }
    return 0;
}