题解：UVA10359 Tiling

· · 题解

UVA10359 Tiling 题解

FFT 好题

易发现可用 dp 求解，设 f(x) 为拼出长为 2 的图形的方案数。

题目描述了要拼成一个 2×n 的图案，有以下 3 种方案：

所以易推出 f(x)=f(x-1)+2×f(x-2)。

由于每次至少乘 2 所以需要用高精度。

在乘 2 的时候可以用 FFT 解决。

Code:

//f[i]=f[i-1]+2*f[i-2]
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
const int N=1<<22;
const double Pi=acos(-1.0); 
int aa[1000000],bb[1000000],anss[1000000];
string add(string s1,string s2){
    memset(anss,0,sizeof(anss));
    memset(aa,0,sizeof(aa));
    memset(bb,0,sizeof(bb));
    for(int i=0;i<s1.size();i++) aa[i+1]=s1[i]-'0';
    for(int i=0;i<s2.size();i++) bb[i+1]=s2[i]-'0';
    reverse(aa+1,aa+s1.size()+1);
    reverse(bb+1,bb+s2.size()+1);
    int len=max(s1.size(),s2.size());
    for(int i=1;i<=len;i++){
        anss[i]+=aa[i]+bb[i];
        anss[i+1]+=anss[i]/10;
        anss[i]%=10;
    }
    bool flag=0;
    if(anss[len+1]!=0) flag=1;
    string res="";
    for(int i=len+flag;i>=1;i--) res+=char(anss[i]+'0');
    return res;
}
struct complex{
    double x,y;
    complex (double xx=0,double yy=0){x=xx,y=yy;}
}a[N],b[N];
complex operator + (complex a,complex b){return complex(a.x+b.x,a.y+b.y);} 
complex operator - (complex a,complex b){return complex(a.x-b.x,a.y-b.y);} 
complex operator * (complex a,complex b){return complex(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);}
void FFT(int limit,complex *a,int type){
    if(limit == 1) return;
    complex 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];
    FFT(limit>>1,a1,type);
    FFT(limit>>1,a2,type);
    complex Wn=complex(cos(2.0*Pi/limit) , type*sin(2.0*Pi/limit)),w=complex(1,0);
    for(int i=0;i<(limit>>1);i++,w=w*Wn) 
        a[i]=a1[i]+w*a2[i],
        a[i+(limit>>1)]=a1[i]-w*a2[i]; 
} 
int n,m,ans[N];
string mul(string s1,string s2){
    memset(ans,0,sizeof ans);
    n=s1.size(),m=s2.size(); 
    reverse(s1.begin(),s1.end());
    reverse(s2.begin(),s2.end());
    for(int i=0;i<n;i++) a[i].x=s1[i]-'0';
    for(int i=0;i<m;i++) b[i].x=s2[i]-'0';
    int limit=1;while(limit<=n+m-2) limit<<=1;
    FFT(limit,a,1);
    FFT(limit,b,1);
    for(int i=0;i<=limit;i++)
        a[i]=a[i]*b[i];
        FFT(limit,a,-1);
    for(int i=0;i<=n+m-1;i++)
        ans[i]=(int)(a[i].x/limit+0.5);
    for(int i=0;i<n+m-1;i++){
        ans[i+1]+=ans[i]/10;
        ans[i]%=10;
    }
    int flag=1;
    string res="";
    for(int i=n+m-1;i>=0;i--){
        if(flag && ans[i]==0) continue;
        res+=char(ans[i]+'0');
        flag=0;
    }
    return res;
}
string dp[255];
int main(){
    string sss="2";
    for(int i=0;i<=250;i++) dp[i]="0";
    dp[0]="1",dp[1]="1",dp[2]="3";
    for(int i=3;i<=250;i++){
        string tmp=add(dp[i-2],dp[i-2]);
        dp[i]=add(dp[i-1],tmp);
    }
    int q;
    while(cin>>q){
        cout<<dp[q]<<endl;
    }
}