题解：UVA10359 Tiling

damnM3bro · 2025-03-26 17:07:49 · 题解

思路

首先，很容易看出本题考查的算法为动态规划。\ 设 dp_i 为摆出 2\times n 的长方形的方案数，考虑如何转移。

不难发现 2\times n 的长方形既可以由 2\times(n-1) 与 2\times 1 的长方形拼出，也可以由 2\times(n-2) 与两块 1\times 2 或 2\times 1 的长方形拼出。

即 dp_i=2\times dp_{i-2}+dp_{i-1}。

注意事项

本题答案的值可能极大，需要使用高精度加法与高精度乘法。（其实可以不用高精度乘法）

注：为了追求效率，我使用了快速傅里叶变换以实现高精乘。

代码（码风猎奇）

#include<bits/stdc++.h>
using namespace std;
const int N=257,M=1007;
const double Pi=acos(-1.0);
int n,lg[M];
string dp[N];

string High_precision_addition(string a,string b){
    int ans[max(a.size(),b.size())+7]={0};
    if(a.size()>b.size())
        swap(a,b);
    while(a.size()<b.size())
        a='0'+a;
    for(int i=0;i<a.size();++i)
        ans[i]=(a[a.size()-i-1]-'0'+b[a.size()-i-1]-'0');
    for(int i=0;i<a.size();++i){
        ans[i+1]+=ans[i]/10;
        ans[i]%=10;
    }
    string res="";
    if(ans[a.size()])
        res+=char(ans[a.size()]+'0');
    for(int i=a.size()-1;i>=0;--i)
        res+=char(ans[i]+'0');
    return res;
}

void Fast_Fourier_Transform(int limit,complex<double> *a,int type){
    if(limit==1)
        return;
    complex<double> a1[limit>>1],a2[limit>>1];
    for(int i=0;i<limit;i+=2){
        a1[i>>1]=a[i];
        a2[i>>1]=a[i+1];
    }
    Fast_Fourier_Transform(limit>>1,a1,type);
    Fast_Fourier_Transform(limit>>1,a2,type);
    complex<double> w{1,0};
    complex<double> wn{cos(2*Pi/limit),type*sin(2*Pi/limit)};
    for(int i=0;i<limit>>1;++i,w*=wn){
        a[i]=a1[i]+a2[i]*w;
        a[i+(limit>>1)]=a1[i]-a2[i]*w;
    }
}

string High_precision_multiplication(string a,string b){
    complex<double> f[1<<(lg[max(a.size(),b.size())]+1)];
    complex<double> g[1<<(lg[max(a.size(),b.size())]+1)];
    int ans[M]={0};
    for(int i=1;i<=a.size();++i)
        f[i-1]=a[a.size()-i]-'0';
    for(int i=1;i<=b.size();++i)
        g[i-1]=b[b.size()-i]-'0';
    int lt=1;
    while(lt<=a.size()+b.size()-1)
        lt<<=1;
    Fast_Fourier_Transform(lt,f,1);
    Fast_Fourier_Transform(lt,g,1);
    for(int i=0;i<=lt;++i)
        f[i]*=g[i];
    Fast_Fourier_Transform(lt,f,-1);
    for(int i=0;i<=a.size()+b.size()-1;++i)
        ans[i]=(int)(f[i].real()/lt+0.5);
    for(int i=0;i<a.size()+b.size()-1;++i){
        ans[i+1]+=ans[i]/10;
        ans[i]=ans[i]%10;
    }
    string res="";
    bool flg=true;
    for(int i=a.size()+b.size()-1;i>=0;--i){
        if(flg&&!ans[i])
            continue;
        else{
            flg=false;
            res+=char(ans[i]+'0');
        }
    }
    return res;
}

int main(){
    dp[0]="1",dp[1]="1",dp[2]="3";
    for(int i=2;i<M;++i)
        lg[i]=lg[i>>1]+1;
    for(int i=3;i<=250;++i)
        dp[i]=High_precision_addition(dp[i-1],
        High_precision_multiplication("2",dp[i-2]));
    while(cin>>n)
        cout<<dp[n]<<"\n";
    return 0;
}