P3341 [ZJOI2014] 消棋子

首先要找到一个策略，能用最少步数揭开这个东西。
发现对于任意 \(x\)，第 \(1\) 到 \(x-1\) 个环都不受 \(x\) 的影响。
假设我们要解 \(n\) 个环，可以先把前 \(n-2\) 个环卸下，把第 \(n\) 个环卸下，把前 \(n-2\) 个环装上，把前 \(n-1\) 个环卸下。
得到递推式 \(f_i=f_{i-2}\times2+f_{i-1}+1\),边界为 \(f_0=0,f_1=1\)。由于答案过大，要用高精度，但这样太慢了，需要矩阵乘法优化。
但是这太复杂了。
设 \(G(x)=\sum_{i=1}^{\infty}f_ix^i\)。
根据递推式，有 \(\sum_{i=2}^{\infty}f_ix^i-\sum_{i=2}^{\infty}f_{i-1}x^i-\sum_{i=2}^{\infty}2f_{i-2}x^i=\sum_{i=2}^{\infty}x^i\)
即 \((G(x)-f_1x)-G(x)x-2G(x)x^2=\frac{x^2}{1-x}\)
化简得 \(G(x)=\frac x{(1-x)(1-x-2x^2)}=\frac x{(1-x)(1+x)(1-2x)}\)
设 \(\frac x{(1-x)(1+x)(1-2x)}=\frac A{1-x}+\frac B{1+x}+\frac C{1-2x}\)
即 \(x=(1+x)(1-2x)A+(1-x)(1-2x)B+(1-x)(1+x)C\)
分别令 \(x=1,-1,\frac12\)，得 \(A=-\frac12,B=-\frac16,C=\frac23\)
所以 \(G(x)=-\frac12\cdot\frac1{1-x}-\frac16\cdot\frac1{1+x}+\frac23\cdot\frac1{1-2x}\)
由公式 \(\frac1{1-rx}=\sum_{i=1}^{\infty}(rx)^i\)
得 \(G(x)=-\frac12\sum_{i=1}^{\infty}x^i-\frac16\sum_{i=1}^{\infty}(-1)^ix^i+\frac23\sum_{i=1}^{\infty}2^ix^i\)
对比同次项系数得 \(f_i=-\frac12-\frac16(-1)^i+\frac232^i\)
化简 \(f_i=\frac{2^{i+2}-3-(-1)^i}6\)
分类讨论

1. 当 \(n\) 是奇数时
   \(f_i=\frac{2^{n+1}}3-\frac{3-1}6=\frac{2^{n+1}}3-\frac13=\lfloor\frac{2^{n+1}}{3}\rfloor\)
2. 当 \(n\) 是偶数时
   \(f_i=\frac{2^{n+1}}3-\frac{3+1}6=\frac{2^{n+1}}3-\frac23=\lfloor\frac{2^{n+1}}{3}\rfloor\)

得出结合两种情况得出\(f_i=\lfloor\frac{2^{n+1}}{3}\rfloor\)。

代码

写的是矩阵乘法优化 \(dp\)，乘法用的是 \(FFT\)。

/*
Luogu P4461 [CQOI2018] 九连环
2026-03-23
*/
#include<bits/stdc++.h>
using namespace std;
namespace IO{
    template<typename T>
    inline void read(T&x){
        x=0;char c=getchar();bool f=0;
        while(!isdigit(c)) c=='-'?f=1:0,c=getchar();
        while(isdigit(c)) x=x*10+c-'0',c=getchar();
        f?x=-x:0;
    }
    template<typename T>
    inline void write(T x){
        if(x==0){putchar('0');return ;}
        x<0?x=-x,putchar('-'):0;short st[50],top=0;
        while(x) st[++top]=x%10,x/=10;
        while(top) putchar(st[top--]+'0');
    }
    inline void read(char&c){c=getchar();while(isspace(c)) c=getchar();}
    inline void write(char c){putchar(c);}
    inline void read(string&s){s.clear();char c;read(c);while(!isspace(c)&&~c) s+=c,c=getchar();}
    inline void write(string s){for(int i=0,len=s.size();i<len;i++) putchar(s[i]);}
    template<typename T>inline void write(T*x){while(*x) putchar(*(x++));}
    template<typename T,typename...T2> inline void read(T&x,T2&...y){read(x),read(y...);}
    template<typename T,typename...T2> inline void write(const T x,const T2...y){write(x),putchar(' '),write(y...),sizeof...(y)==1?putchar('\n'):0;}
}using namespace IO;
#define C complex<double>
const double PI=3.14159265358979323846;
void FFT(C a[],int n,bool flag){
    if(n==1) return ;
    C a0[n/2],a1[n/2];
    for(int i=0;i<n/2;i++) a0[i]=a[i<<1],a1[i]=a[i<<1|1];
    FFT(a0,n/2,flag),FFT(a1,n/2,flag);
    C w=1,dwg;
    if(flag) dwg.real(cos(-2*PI/n)),dwg.imag(sin(-2*PI/n));
    else dwg.real(cos(2*PI/n)),dwg.imag(sin(2*PI/n));
    for(int i=0;i<n/2;i++){
        a[i]=a0[i]+w*a1[i];
        a[i+n/2]=a0[i]-w*a1[i];
        w*=dwg;
    }
}
void mul(vector<int>&a,vector<int>&b){
    int n=1<<__lg(a.size()+b.size())+1;
    C A[n],B[n];
    for(int i=0;i<a.size();i++) A[i]=a[i];
    for(int i=0;i<b.size();i++) B[i]=b[i];
    FFT(A,n,0),FFT(B,n,0);
    for(int i=0;i<n;i++) A[i]*=B[i];
    FFT(A,n,1);
    a.resize(n);
    for(int i=0;i<n;i++) a[i]=(int)round(A[i].real()/n);
    for(int i=0;i<n-1;i++) a[i+1]+=a[i]/10,a[i]%=10;
    while(!a.empty()&&!a.back()) a.pop_back();
}
struct Int{
    vector<int>a;
    friend void write(Int x){
        if(x.a.size()==0){write(0);return ;}
        for(int i=x.a.size()-1;i>=0;i--) write(x.a[i]);
    }
    Int(int x){while(x) a.push_back(x%10),x/=10;}
    Int(){a.clear();}
    void clear(){a.clear();}
    Int operator+(const Int x)const{
        vector<int>b=x.a,a=this->a;
        int n=max(b.size(),a.size());
        b.resize(n+1),a.resize(n+1);
        for(int i=0;i<n;i++) a[i]+=b[i];
        for(int i=0;i<n;i++) a[i+1]+=a[i]/10,a[i]%=10;
        while(!a.empty()&&!a.back()) a.pop_back();
        Int A;
        A.a.swap(a);
        return{A};
    }
    Int operator*(const Int x)const{
        vector<int>a=this->a,b=x.a;
        mul(a,b);
        Int A;
        A.a.swap(a);
        return{A};
    }
};
template<typename T,int maxn>struct Matrix{
    T a[maxn+10][maxn+10];
    Matrix(){memset(a,0,sizeof(a));}
    Matrix operator*(const Matrix b){
        Matrix c;
        for(int i=1;i<=maxn;i++) for(int k=1;k<=maxn;k++) for(int j=1;j<=maxn;j++) c.a[i][j]=c.a[i][j]+a[i][k]*b.a[k][j];
        return c;
    }
};
const int maxn=100010;
Matrix<Int,3>f,base;
int n;
void solve(){
    read(n);
    if(n==1){write("1\n");return ;}
    if(n==2){write("2\n");return ;}
    f.a[1][1]=2,f.a[1][2]=1,f.a[1][3]=1;
    f.a[2][1]=0,f.a[2][2]=0,f.a[2][3]=0;
    f.a[3][1]=0,f.a[3][2]=0,f.a[3][3]=0;
    base.a[1][1]=1,base.a[1][2]=1,base.a[1][3]=0;
    base.a[2][1]=2,base.a[2][2]=0,base.a[2][3]=0;
    base.a[3][1]=1,base.a[3][2]=0,base.a[3][3]=1;
    n-=2;
    while(n){
        if(n&1) f=f*base;
        base=base*base;
        n>>=1;
    }
    write(f.a[1][1]);write("\n");
}
signed main(){
    int T;read(T);
    while(T--) solve();
    return 0;
}