P2561 [AHOI2002]黑白瓷砖

大致思路就是将图案分为一个个环套在一起，

然后用图来观察关系，再用容斥原理dp即可。

#include<iostream>
#include<memory.h>
#include<algorithm>
#define maxlon 100
using namespace std;

struct bigmun{
    int s[maxlon],lon;
    void clear(){
        for(int i=lon;i>=0;i--)
        if(s[i]){lon=i;break;}
    }
    void csh(){
        memset(s,0,sizeof(s));
        lon=0;
    }
    bigmun operator -(const bigmun &b)const{
        bigmun Ans=*this;
        for(int i=b.lon;i>=0;i--)
            Ans.s[i]-=b.s[i];
        for(int i=0;i<=Ans.lon;i++)
        if(Ans.s[i]<0)
        Ans.s[i+1]--,Ans.s[i]+=10;
        Ans.clear();
        return Ans;
    }
    bigmun operator +(const bigmun &b)const{
        bigmun Ans=*this;
        Ans.lon=max(Ans.lon,b.lon)+1;
        for(int i=b.lon;i>=0;i--)
            Ans.s[i]+=b.s[i];
        for(int i=0;i<=Ans.lon;i++)
        if(Ans.s[i]>=10)
        Ans.s[i+1]++,Ans.s[i]-=10;
        Ans.clear();
        return Ans;
    }
    bigmun operator *(const bigmun &b)const{
        //cout<<"cz:\n";
        bigmun Ans;Ans.lon=b.lon+lon+1;
        memset(Ans.s,0,sizeof(Ans.s));
        for(int i=0;i<=lon;i++)
        for(int j=0;j<=b.lon;j++)
        Ans.s[i+j]+=s[i]*b.s[j];
        for(int i=0;i<=Ans.lon;i++)
        if(Ans.s[i]>=10)
        Ans.s[i+1]+=Ans.s[i]/10,
        Ans.s[i]%=10;
        Ans.clear();
        //Ans.coutt();
        return Ans;
    }
    bigmun cheng(int n){
        for(int i=0;i<=lon;i++)s[i]*=n;
        for(int i=0;i<=lon;i++)
        if(s[i]>=10)
        s[i+1]+=s[i]/10,s[i]%=10;
        lon++;
        clear();
        return *this;
    }
    void chu(int b){
        bigmun Ans;Ans.csh();Ans.lon=lon;
        int c=0,cur=lon;
        while(cur>=0){
            c=c*10+s[cur];
            if(c>=b){
                Ans.s[cur]+=c/b;
                c%=b;
            }
            cur--;
        }
        Ans.clear();
        *this=Ans;
    }
    void coutt(){
        for(int i=lon;i>=0;i--)
        cout<<s[i];
        cout<<endl;//
    }
}mi2[211],ans[4];
void csh(){
    mi2[0].csh();mi2[0].s[0]=1;
    mi2[1].csh();mi2[1].s[0]=2;
    for(int i=1;i<=210;i++)
    mi2[i]=mi2[i-1]*mi2[1];//,mi2[i].coutt();
    ans[1].csh();ans[1].s[0]=1;
}
int n,tot;
int f[4];//3xuanfan,1kexuanzhuan,2kefanzhuan;
int main(){
    cin>>n;if(n==1){cout<<2;return 0;}
    csh();int nn=n;
    while(nn>0){
        if(nn==n){
            ans[1]=(mi2[nn-1]-mi2[(nn+1)/2]);
            ans[1].chu(2);
        }
        else if(nn==1)ans[1].cheng(2);
        else if(nn==2)ans[1].cheng(2);
        else if(nn==3)ans[1].cheng(4);
        else{
            bigmun a2=(mi2[nn-1]-mi2[(nn+1)/2]);
            a2.chu(2);
            ans[1]=mi2[1]*ans[1]*a2+ans[1]*mi2[(nn+1)/2]+a2*mi2[f[3]];
        }
        f[3]+=(nn+1)/2;
        f[2]+=nn-1+(nn+1)/2;
        nn-=3;
        //ans[1].coutt();
    }
    ans[2]=mi2[f[2]];
    ans[3]=mi2[f[3]];
    //ans[1]=ans[1]-ans[3];
    ans[2]=ans[2]-ans[3];
    //ans[1].coutt();
    //ans[2].coutt();
    //ans[3].coutt();
    bigmun Ans=mi2[(n+1)*n/2]+(ans[1].cheng(4))+(ans[2].cheng(3))+(ans[3].cheng(5));
    //mi2[(n+1)*n/2].coutt();
    Ans.chu(6);
    Ans.coutt();
    return 0;
}