史上第二玄学TLE

AlgoEmperor @ 2019-06-18 19:43:05

#include <bits/stdc++.h>
#define MAX 400
using namespace std;

struct Num{
    int size,x[MAX];
}d1,d2,d3;

const int MAXB = 1e9;
int N,x=3;

inline void add(Num &a,const Num &b,Num &ans)
{
    ans.size = a.size;
    for (register int i=1; i<=a.size; i++)
    {
        ans.x[i] = a.x[i] + b.x[i];
        if (ans.x[i] >= MAXB)
        {
            ans.x[i] -= MAXB;
            a.x[i+1]++;
        }
    }
    if (ans.x[ans.size+1]) ans.size++;
    x = (x==3) ? 1 : x+1;
}

inline void print(const Num &ans)
{
    cout << ans.x[ans.size];
    cout << setw(10) << setfill('0'); 
    for (register int i=ans.size-1; i>=1; i--)
        cout << ans.x[i];
}

int main()
{
    ios::sync_with_stdio(0);
    cin >> N; N -= 2;
    d1.x[1] = 1; d2.x[1] = 2;
    d1.size = d2.size = 1;
    while (N--){
        if (x == 1) add(d2,d1,d3);
        if (x == 2) add(d3,d2,d1);
        if (x == 3) add(d1,d3,d2);
    }
    if (x == 1) print(d2);
    if (x == 2) print(d3);
    if (x == 3) print(d1);
}

by mulberror @ 2019-06-18 20:18:34

@树链剖分 %%%

by ZhuMingYang @ 2019-06-18 20:21:48

@Ofnoname

反手抛个高精

struct node
{
    int arr[1000],len;
    node()
    {
        memset(arr,0,sizeof(arr));
        len=0;
    }
    void print()
    {
        printf("%d",arr[len]);
        dwn(i,len-1,0)
        {
            printf("%04d",arr[i]);
        }
        putchar('\n');
    }
}ans;
node operator +(node a,node b)
{
    node c;c.len=max(a.len,b.len);int x=0;
    rep(i,0,c.len)
    {
        c.arr[i]=a.arr[i]+b.arr[i]+x;
        x=c.arr[i]/p;
        c.arr[i]%=p;
    }
    if(x>0)
        c.arr[++c.len]=x;
    return c;
}
node operator *(node a,int b)
{
    if(b==0)
    {
        node c;
        return c;
    }
    node c;c.len=a.len;ll x=0;
    rep(i,0,c.len)
    {
        c.arr[i]=(1ll*a.arr[i]*b+x)%p;
        x=(x+1ll*a.arr[i]*b)/p;
    }
    while(x>0)
    {
        c.arr[++c.len]=x%p;
        x/=p;
    }
    return c;
}
node arrmax(node a,node b)
{
    if(a.len>b.len)
        return a;
    else if(a.len<b.len)
        return b;
    dwn(i,a.len,0)
    {
        if(a.arr[i]>b.arr[i])
            return a;
        else if(a.arr[i]<b.arr[i])
            return b;
    }
    return a;
}
node operator /(node a,int b)
{
    node c;c.len=a.len;ll x=0;
    dwn(i,c.len,0)
    {
        c.arr[i]=(a.arr[i]+x*p)/b;
        x=(a.arr[i]+x*p)%b;
    }
    dwn(i,c.len,1)
    {
        if(c.arr[i]==0) c.len--;
        else break;
    }
    return c;
}