BZOJ1002 윤상 바이러스

[BZOJ1002] FJOI 2007 휠체어 바이러스 못해, 결론 문제...
카탈로그

결론

코드

결론

주동 2007년 합숙팀 논문의 일부 신기한 이론에서 알 수 있듯이 i개 점의 생성 나무 개수의 추이식 형식은 dp[i]=3∗dp[i-1]--dp[i-3]+2]+2이기 때문에 함부로 하면 된다.

코드

#include 
#include 
#include 
#include 

using std::max;
using std::cout;
using std::ostream;
using std::memset;

const int MAXN=105;
int n;

class bigNum{
    private:
        int c[MAXN];
    public:
        bigNum(){memset(c,0,sizeof(c));}
        void init(int len,int x){
            c[0]=len,c[1]=x;
        }
        friend bigNum operator+ (const bigNum &a,const int b){
            bigNum c;
            c.c[1]=b;
            for(int i=1;i<=a.c[0];++i){
                c.c[i]+=a.c[i];
                c.c[i+1]+=c.c[i]/10;
                c.c[i]%=10;
            }
            c.c[0]=a.c[0];
            if(c.c[c.c[0]]>9){
                c.c[c.c[0]+1]+=c.c[c.c[0]]/10;
                c.c[c.c[0]]%=10;
                ++c.c[0];
            }
            return c;
        }
        friend bigNum operator- (const bigNum &a,const bigNum &b){
            bigNum c;
            for(int i=1;i<=a.c[0];++i){
                c.c[i]+=a.c[i]-b.c[i];
                if(c.c[i]<0){
                    c.c[i]+=10;
                    --c.c[i+1];
                }
            }
            c.c[0]=a.c[0];
            while(c.c[c.c[0]]==0) --c.c[0];
            return c;
        }
        friend bigNum operator* (const bigNum &a,const int b){
            bigNum c;
            for(int i=a.c[0];i;--i){
                c.c[i]=a.c[i]*b;
                c.c[i+1]+=c.c[i]/10;
                c.c[i]%=10;
            }
            c.c[0]=a.c[0];
            while(c.c[c.c[0]]>9){
                c.c[c.c[0]+1]+=c.c[c.c[0]]/10;
                c.c[c.c[0]]%=10;
                ++c.c[0];
            }
            while(c.c[c.c[0]+1]) ++c.c[0];
            return c;
        }
        friend ostream& operator<< (ostream &out,const bigNum &a){
            for(int i=a.c[0];i;--i)
                putchar(a.c[i]|'0');
            return out;
        }
}dp[MAXN];

int main(){
    scanf("%d",&n);
    dp[1].init(1,1);
    dp[2].init(1,5);
    for(int i=3;i<=n;++i)
        dp[i]=dp[i-1]*3-dp[i-2]+2;
    cout<return 0;
}